この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

オートマトン・形式言語の問題

難易度 4大学院入試の標準レベル大学数学オートマトン・形式言語

終端記号 ${a}$ 、非終端記号 ${S, T}$ 、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$S \to S S ∣ S T ∣ a, T \to S S$
文字列 $aaaaaa$ （ $a$ を $6$ 個並べた文字列 $a^{6}$ ）の、 $G$ における最左導出の個数を求めよ。

この問題で使うもの

導出木の個数の数え上げ（説明と入口の問題）
文脈自由文法の導出と導出木（説明と入口の問題）

この問題を解けるようになるまで（3 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

最左導出と導出木は 1 対 1 に対応するので、 $a^{6}$ の導出木の個数を数えればよい。文字列が $a$ だけなので、部分文字列は長さだけで区別すれば十分。

ヒント 2

$a^{n}$ を $S$ から導く導出木の数を $g (n)$ 、 $T$ から導く数を $t (n)$ とおくと、 $t (n) = \sum_{i = 1}^{n - 1} g (i) g (n - i)$ 、 $g (n) = t (n) + \sum_{i = 1}^{n - 1} g (i) t (n - i)$ （ $n \geq 2$ ）、 $g (1) = 1, t (1) = 0$ 。

ヒント 3

CYK 法の表のように長さの短い順に計算すると、 $g (1), \dots, g (4) = 1, 1, 3, 10$ 、 $t (1), \dots, t (4) = 0, 1, 2, 7$ となる。続けて $n = 5, 6$ を計算する。

答えと解説

答えを見る

154

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

文脈自由文法では、ある文字列の最左導出と、その文字列の導出木（構文木）は 1 対 1 に対応する。そこで導出木の個数を数える。

$G$ はチョムスキー標準形なので、CYK 法と同じように、部分文字列ごとに「各非終端記号から何通りの導出木で導けるか」を表にする。文字列は $a$ だけからなるので、部分文字列は長さだけで決まる。長さ $n$ の文字列 $a^{n}$ を $S$ から導く導出木の個数を $g (n)$ 、 $T$ から導く導出木の個数を $t (n)$ とする。

漸化式. 長さ $n$ の文字列を、根の規則が 2 つの非終端記号に分ける位置で場合分けする。
- $T \to S S$ だけが $T$ の規則なので、 $n \geq 2$ で
$t (n) = i = 1 \sum n - 1 g (i) g (n - i), t (1) = 0.$
- $S$ の規則は $S \to S S$ , $S \to S T$ , $S \to a$ 。よって $g (1) = 1$ （ $S \to a$ ）、 $n \geq 2$ で
$g (n) = i = 1 \sum n - 1 g (i) g (n - i) + i = 1 \sum n - 1 g (i) t (n - i) = t (n) + i = 1 \sum n - 1 g (i) t (n - i) .$

表の計算.
- $n = 1$ : $g (1) = 1$ , $t (1) = 0$ 。
- $n = 2$ : $t (2) = g (1) g (1) = 1$ 。 $g (2) = t (2) + g (1) t (1) = 1 + 0 = 1$ 。
- $n = 3$ : $t (3) = g (1) g (2) + g (2) g (1) = 1 + 1 = 2$ 。 $g (3) = 2 + (g (1) t (2) + g (2) t (1)) = 2 + (1 + 0) = 3$ 。
- $n = 4$ : $t (4) = g (1) g (3) + g (2) g (2) + g (3) g (1) = 3 + 1 + 3 = 7$ 。 $g (4) = 7 + (g (1) t (3) + g (2) t (2) + g (3) t (1)) = 7 + (2 + 1 + 0) = 10$ 。
- $n = 5$ : $t (5) = g (1) g (4) + g (2) g (3) + g (3) g (2) + g (4) g (1) = 10 + 3 + 3 + 10 = 26$ 。 $g (5) = 26 + (g (1) t (4) + g (2) t (3) + g (3) t (2) + g (4) t (1)) = 26 + (7 + 2 + 3 + 0) = 38$ 。
- $n = 6$ : $t (6) = g (1) g (5) + g (2) g (4) + g (3) g (3) + g (4) g (2) + g (5) g (1) = 38 + 10 + 9 + 10 + 38 = 105$ 。
$g (6) = 105 + (g (1) t (5) + g (2) t (4) + g (3) t (3) + g (4) t (2) + g (5) t (1)) = 105 + (26 + 7 + 6 + 10 + 0) = 154.$

$n$	1	2	3	4	5	6
$t (n)$	0	1	2	7	26	105
$g (n)$	1	1	3	10	38	154

よって $a^{6}$ の最左導出の個数は $154$ である。

（参考: $S \to S T, T \to S S$ の組は「 $S$ を 3 つに分ける」ことに当たるので、 $g (n)$ は各内部節点の子が 2 個または 3 個の順序木で葉が $n$ 個のものの個数に等しい。）

別解

文法は曖昧でも、各導出木にはちょうど 1 つの最左導出が対応するので、最左導出の個数は導出木の個数に等しい。 $s_{n}, t_{n}$ を、それぞれ $S$ から $a^{n}$ 、 $T$ から $a^{n}$ を導く導出木（最左導出）の個数とする。

規則から（チョムスキー標準形で、 $S \to S S ∣ S T ∣ a$ , $T \to S S$ ）
$c_{n} = k = 1 \sum n - 1 s_{k} s_{n - k}, t_{n} = c_{n}, s_{n} = [n = 1] + c_{n} + k = 1 \sum n - 1 s_{k} t_{n - k} .$

$n = 1$ : $s_{1} = 1$ , $t_{1} = 0$ 。
$n = 2$ : $c_{2} = s_{1} s_{1} = 1$ , $t_{2} = 1$ , $s_{2} = 1 + s_{1} t_{1} = 1$ 。
$n = 3$ : $c_{3} = s_{1} s_{2} + s_{2} s_{1} = 2$ , $t_{3} = 2$ , $s_{3} = 2 + (s_{1} t_{2} + s_{2} t_{1}) = 2 + 1 = 3$ 。
$n = 4$ : $c_{4} = s_{1} s_{3} + s_{2} s_{2} + s_{3} s_{1} = 3 + 1 + 3 = 7$ , $t_{4} = 7$ , $s_{4} = 7 + (s_{1} t_{3} + s_{2} t_{2} + s_{3} t_{1}) = 7 + (2 + 1 + 0) = 10$ 。
$n = 5$ : $c_{5} = s_{1} s_{4} + s_{2} s_{3} + s_{3} s_{2} + s_{4} s_{1} = 10 + 3 + 3 + 10 = 26$ , $t_{5} = 26$ , $s_{5} = 26 + (s_{1} t_{4} + s_{2} t_{3} + s_{3} t_{2} + s_{4} t_{1}) = 26 + (7 + 2 + 3 + 0) = 38$ 。
$n = 6$ : $c_{6} = s_{1} s_{5} + s_{2} s_{4} + s_{3} s_{3} + s_{4} s_{2} + s_{5} s_{1} = 38 + 10 + 9 + 10 + 38 = 105$ , $t_{6} = 105$ , $s_{6} = 105 + (s_{1} t_{5} + s_{2} t_{4} + s_{3} t_{3} + s_{4} t_{2} + s_{5} t_{1}) = 105 + (26 + 7 + 6 + 10 + 0) = 154$ 。

よって求める個数は $s_{6} = 154$ 。

検算: $n = 3$ を直接数えると、 $S \to S S$ で分割 $(1, 2), (2, 1)$ の 2 通り、 $S \to S T$ で $S = a$ , $T = aa$ の 1 通り、合計 3 で $s_{3} = 3$ と一致する。

オートマトン・形式言語の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題