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

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

難易度 1教科書の例題レベル大学数学オートマトン・形式言語

終端記号 ${a, b}$ 、非終端記号 ${S, L, R}$ 、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$S \to L S ∣ S R ∣ b, L \to a, R \to a$
文字列 $w = aaba$ の $G$ における導出木（開始記号 $S$ を根とし、葉を左から読むと $w$ になるもの）の個数を求めよ。

この問題で使うもの

導出木の個数の数え上げ（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

CYK 法の表を、非終端記号の集合ではなく「 $X$ が $w_{i .. j}$ を生成する導出木の個数 $N_{X} (i, j)$ 」で埋めていく技能を使います。

ヒント 2

$N_{S} (i, j) = \sum_{k} (N_{L} (i, k) N_{S} (k + 1, j) + N_{S} (i, k) N_{R} (k + 1, j))$ を使います。 $L, R$ は 1 文字しか生成しないので、長さ 2 以上の欄では $N_{L} = N_{R} = 0$ です。

ヒント 3

長さ 2 では $N_{S} (1, 2) = 0$ 、 $N_{S} (2, 3) = 1$ 、 $N_{S} (3, 4) = 1$ 、長さ 3 では $N_{S} (1, 3) = 1$ 、 $N_{S} (2, 4) = 2$ となります。残るのは全体の欄 $(1, 4)$ で、 $k = 1, 2, 3$ の寄与を足すだけです。

答えと解説

答えを見る

3

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

解説を読む

$w = w_{1} w_{2} w_{3} w_{4} = a a b a$ とし、 $N_{X} (i, j)$ を「非終端記号 $X$ を根として部分文字列 $w_{i .. j}$ を生成する導出木の個数」とする。CYK 法の表の各欄に、非終端記号の集合の代わりにこの個数を記録する。

漸化式. 長さ 1 の欄は、規則 $X \to w_{i}$ があれば $N_{X} (i, i) = 1$ 、なければ $0$ である。長さ 2 以上の欄では、 $X \to Y Z$ という規則と分割位置 $k$ （ $i \leq k < j$ ）ごとに、左側 $w_{i .. k}$ の導出木と右側 $w_{k + 1.. j}$ の導出木を自由に組み合わせられるので
$N_{X} (i, j) = X \to Y Z \sum k = i \sum j - 1 N_{Y} (i, k) N_{Z} (k + 1, j)$
となる。 $L, R$ は終端記号 1 文字しか生成しないので、長さ 2 以上では $N_{L} = N_{R} = 0$ である。よって長さ 2 以上では $N_{S}$ だけを計算すればよく、
$N_{S} (i, j) = k = i \sum j - 1 (N_{L} (i, k) N_{S} (k + 1, j) + N_{S} (i, k) N_{R} (k + 1, j))$
である。

長さ 1.
- $(1, 1) = a$ : $N_{L} = 1, N_{R} = 1, N_{S} = 0$
- $(2, 2) = a$ : $N_{L} = 1, N_{R} = 1, N_{S} = 0$
- $(3, 3) = b$ : $N_{S} = 1$ （ $L, R$ は $0$ ）
- $(4, 4) = a$ : $N_{L} = 1, N_{R} = 1, N_{S} = 0$

長さ 2.
- $(1, 2) = aa$ : $k = 1$ のみ。 $N_{L} (1, 1) N_{S} (2, 2) + N_{S} (1, 1) N_{R} (2, 2) = 1 \cdot 0 + 0 \cdot 1 = 0$ 。
- $(2, 3) = ab$ : $N_{L} (2, 2) N_{S} (3, 3) + N_{S} (2, 2) N_{R} (3, 3) = 1 \cdot 1 + 0 \cdot 0 = 1$ 。
- $(3, 4) = ba$ : $N_{L} (3, 3) N_{S} (4, 4) + N_{S} (3, 3) N_{R} (4, 4) = 0 \cdot 0 + 1 \cdot 1 = 1$ 。

長さ 3.
- $(1, 3) = aab$ :
- $k = 1$ : $N_{L} (1, 1) N_{S} (2, 3) + N_{S} (1, 1) N_{R} (2, 3) = 1 \cdot 1 + 0 = 1$
- $k = 2$ : $N_{L} (1, 2) N_{S} (3, 3) + N_{S} (1, 2) N_{R} (3, 3) = 0 + 0 = 0$
- よって $N_{S} (1, 3) = 1$ 。
- $(2, 4) = aba$ :
- $k = 2$ : $N_{L} (2, 2) N_{S} (3, 4) + N_{S} (2, 2) N_{R} (3, 4) = 1 \cdot 1 + 0 = 1$
- $k = 3$ : $N_{L} (2, 3) N_{S} (4, 4) + N_{S} (2, 3) N_{R} (4, 4) = 0 + 1 \cdot 1 = 1$
- よって $N_{S} (2, 4) = 2$ 。

長さ 4（全体）. $(1, 4) = aaba$ :
- $k = 1$ : $N_{L} (1, 1) N_{S} (2, 4) + N_{S} (1, 1) N_{R} (2, 4) = 1 \cdot 2 + 0 = 2$
- $k = 2$ : $N_{L} (1, 2) N_{S} (3, 4) + N_{S} (1, 2) N_{R} (3, 4) = 0 + 0 = 0$
- $k = 3$ : $N_{L} (1, 3) N_{S} (4, 4) + N_{S} (1, 3) N_{R} (4, 4) = 0 + 1 \cdot 1 = 1$

したがって $N_{S} (1, 4) = 2 + 0 + 1 = 3$ 。

確認. この文法は、中心の $b$ の左にある $a$ を $L$ で、右にある $a$ を $R$ で 1 つずつはがしていく。左の $a$ 2 個（L, L）と右の $a$ 1 個（R）をはがす順序は $3$ 通りで、表の結果と一致する。

答えは $3$ である。

別解

$G$ では $S \to L S$ は左端に $a$ を 1 つ付け、 $S \to S R$ は右端に $a$ を 1 つ付ける。 $S \to b$ で終了するので、 $L (G) = {a^{i} b a^{j} ∣ i, j \geq 0}$ である。

$w = aaba$ では $b$ の左に $a$ が 2 個、右に $a$ が 1 個ある。 $b$ より左の $a$ は $L \to a$ からしか出ず、右の $a$ は $R \to a$ からしか出ない。したがって導出木は、根から順に「左を 1 つ剥がす ( $S \to L S$ )」を 2 回、「右を 1 つ剥がす ( $S \to S R$ )」を 1 回行い、最後に $S \to b$ を使うものである。

異なる順序は異なる木を与えるので、木の個数は $L, L, R$ の並べ方の数 $(1 3) = 3$ である。

3 つの木は次のとおり。
- $S \to L S \to LL S \to LL S R$
- $S \to L S \to L S R \to LL S R$
- $S \to S R \to L S R \to LL S R$

いずれも最後に $S \to b$ と $L, R \to a$ を使って $aaba$ を得る。

検算として $w = aba$ の場合を調べると、 $L S R$ に至る順序は $L S \to L (S R)$ と $S R \to (L S) R$ の 2 通りで、 $(1 2) = 2$ と一致する。

よって答えは 3。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題