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

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

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

終端記号 ${a, b, c}$ 、非終端記号 ${S, X, Y, A, B, C}$ 、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$S \to X C ∣ A Y ∣ S C, X \to A B, Y \to B C ∣ Y C,$
$A \to a, B \to b, C \to c$
文字列 $w = ab cc$ について、 $S$ を根とし $w$ を生成する導出木（構文木）の個数を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

CYK 法の表の各欄に、非終端記号の集合ではなく「その記号を根としてその部分文字列を生成する導出木の個数」を書き込む方法を使う。

ヒント 2

$N_{Z} (i, j) = \sum_{Z \to P Q} \sum_{k = i}^{j - 1} N_{P} (i, k) N_{Q} (k + 1, j)$ を、長さ 1, 2, 3, 4 の順に計算する。積は左右の部分木の選び方、和は規則と分割位置の違いに対応する。

ヒント 3

長さ 2 では $N_{X} (1, 2) = 1$ 、 $N_{Y} (2, 3) = 1$ 。長さ 3 では $N_{S} (1, 3) = 2$ （ $S \to X C$ と $S \to A Y$ から 1 ずつ）、 $N_{Y} (2, 4) = 1$ （ $Y \to Y C$ から）。あとは全体の欄 $(1, 4)$ で $S \to X C, A Y, S C$ のそれぞれについて分割位置ごとの積を足す。

答えと解説

答えを見る

3

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

解説を読む

$w = w_{1} w_{2} w_{3} w_{4} = ab cc$ とし、 $N_{Z} (i, j)$ を「非終端記号 $Z$ を根として部分文字列 $w_{i .. j}$ を生成する導出木の個数」とする。CYK 法と同じく短い部分文字列から順に表を埋めるが、各欄には集合ではなく個数を記録する。規則 $Z \to P Q$ と分割位置 $k$ $(i \leq k < j)$ について
$N_{Z} (i, j) = Z \to P Q \sum k = i \sum j - 1 N_{P} (i, k) N_{Q} (k + 1, j)$
で計算する（左右の部分木を独立に選べるので積、規則や分割位置が違えば別の木なので和）。

長さ 1： $N_{A} (1, 1) = 1$ 、 $N_{B} (2, 2) = 1$ 、 $N_{C} (3, 3) = 1$ 、 $N_{C} (4, 4) = 1$ 。ほかは $0$ 。

長さ 2：
- $(1, 2) = ab$ ： $X \to A B$ より $N_{X} (1, 2) = N_{A} (1, 1) N_{B} (2, 2) = 1$ 。 $S, Y$ は右辺の各非終端記号が該当する欄に現れないので $0$ 。
- $(2, 3) = b c$ ： $Y \to B C$ より $N_{Y} (2, 3) = N_{B} (2, 2) N_{C} (3, 3) = 1$ 。ほかは $0$ 。
- $(3, 4) = cc$ ：どの規則でも $0$ 。

長さ 3：
- $(1, 3) = ab c$ ：
- $S \to X C$ ： $k = 2$ で $N_{X} (1, 2) N_{C} (3, 3) = 1 \cdot 1 = 1$ （ $k = 1$ は $N_{X} (1, 1) = 0$ ）。
- $S \to A Y$ ： $k = 1$ で $N_{A} (1, 1) N_{Y} (2, 3) = 1 \cdot 1 = 1$ （ $k = 2$ は $N_{Y} (3, 3) = 0$ ）。
- $S \to S C$ ： $N_{S} (1, 1) = N_{S} (1, 2) = 0$ より $0$ 。
よって $N_{S} (1, 3) = 2$ 。 $X, Y$ は $0$ 。
- $(2, 4) = b cc$ ：
- $Y \to B C$ ： $k = 2$ で $N_{B} (2, 2) N_{C} (3, 4) = 1 \cdot 0 = 0$ 。
- $Y \to Y C$ ： $k = 3$ で $N_{Y} (2, 3) N_{C} (4, 4) = 1 \cdot 1 = 1$ 。
よって $N_{Y} (2, 4) = 1$ 。 $S, X$ は $0$ （ $N_{A} (2, 2) = 0$ など）。

ここまでの表（ $0$ でないものだけ記す）：

欄	個数
$(1, 1)$	$A : 1$
$(2, 2)$	$B : 1$
$(3, 3)$	$C : 1$
$(4, 4)$	$C : 1$
$(1, 2)$	$X : 1$
$(2, 3)$	$Y : 1$
$(1, 3)$	$S : 2$
$(2, 4)$	$Y : 1$

長さ 4： $(1, 4) = ab cc$ の $S$ について
- $S \to X C$ ： $k = 1, 2, 3$ で $N_{X} (1, 1) N_{C} (2, 4) = 0$ 、 $N_{X} (1, 2) N_{C} (3, 4) = 1 \cdot 0 = 0$ 、 $N_{X} (1, 3) N_{C} (4, 4) = 0 \cdot 1 = 0$ 。合計 $0$ 。
- $S \to A Y$ ： $k = 1$ で $N_{A} (1, 1) N_{Y} (2, 4) = 1 \cdot 1 = 1$ 。 $k = 2, 3$ は $N_{A} (1, 2) = N_{A} (1, 3) = 0$ で $0$ 。合計 $1$ 。
- $S \to S C$ ： $k = 3$ で $N_{S} (1, 3) N_{C} (4, 4) = 2 \cdot 1 = 2$ 。 $k = 1, 2$ は $N_{S} (1, 1) = N_{S} (1, 2) = 0$ で $0$ 。合計 $2$ 。

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

（確認：3 つの木は $S \to A Y, Y \to Y C, Y \to B C$ のもの、 $S \to S C$ で左の $S$ が $S \to X C$ のもの、 $S \to S C$ で左の $S$ が $S \to A Y$ のもの。）

答え： $3$

別解

CYK 法の要領で、各区間 $[i, j]$ を非終端記号が生成する導出木の個数を数える。 $w = a b c c$ の位置を 1〜4 とする。

長さ 1: $A [1] = 1, B [2] = 1, C [3] = 1, C [4] = 1$ 。

長さ 2:
- $[1, 2]$ : $X \to A B$ より $X = 1$ 。
- $[2, 3]$ : $Y \to B C$ より $Y = 1$ 。
- $[3, 4]$ : $cc$ を生成する規則はないので 0。

長さ 3:
- $[1, 3]$ : $S \to X C$ は $X [1, 2] \cdot C [3] = 1$ 。 $S \to A Y$ は $A [1] \cdot Y [2, 3] = 1$ 。 $S \to S C$ は $S [1, 2] = 0$ なので 0。よって $S [1, 3] = 2$ 。また $X [1, 3] = 0$ 、 $Y [1, 3] = 0$ 。
- $[2, 4]$ : $Y \to B C$ は $C [3, 4]$ が 0 なので 0。 $Y \to Y C$ は $Y [2, 3] \cdot C [4] = 1$ 。よって $Y [2, 4] = 1$ 。

長さ 4、 $S [1, 4]$ :
- $S \to X C$ : $X [1, 3] \cdot C [4] = 0$
- $S \to A Y$ : $A [1] \cdot Y [2, 4] = 1$
- $S \to S C$ : $S [1, 3] \cdot C [4] = 2$

合計は $0 + 1 + 2 = 3$ 。

検算:3 本の木を実際に書き出す。
1. $S \to S C$ 、内側 $S \to X C$ 、 $X \to A B$ 。
2. $S \to S C$ 、内側 $S \to A Y$ 、 $Y \to B C$ 。
3. $S \to A Y$ 、 $Y \to Y C$ 、内側 $Y \to B C$ 。

この 3 本が過不足なく得られる。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題