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

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

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

終端記号 ${a, b}$ 、非終端記号 ${S, A, B, C}$ 、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$S \to A C ∣ B B, A \to a, B \to A S ∣ b, C \to S B ∣ b$
文字列 $w = aabb$ の $i$ 文字目から $j$ 文字目までの部分文字列を $w_{i .. j}$ とし、 $w_{i .. j}$ を導出できる非終端記号全体の集合を $V_{i, j}$ と書く（ $1 \leq i \leq j \leq 4$ ）。CYK 法で表を埋めて、 $V_{1, 4}$ を求めよ。

この問題で使うもの

CYK 法（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

CYK 法を使う。長さ 1 の部分文字列から順に、各部分文字列を導出できる非終端記号の集合を表に書き込んでいく。

ヒント 2

$V_{i, j}$ は、すべての分け目 $k$ （ $i \leq k < j$ ）について $V_{i, k}$ と $V_{k + 1, j}$ から 2 文字の組 $Y Z$ を作り、規則 $X \to Y Z$ の左辺 $X$ を集めたものである。右辺に現れる組は $A C, B B, A S, S B$ の 4 つだけである。

ヒント 3

$V_{1, 1} = V_{2, 2} = {A}$ 、 $V_{3, 3} = V_{4, 4} = {B, C}$ 、 $V_{1, 2} = \emptyset$ 、 $V_{2, 3} = V_{3, 4} = {S}$ 、 $V_{1, 3} = {B}$ 、 $V_{2, 4} = {B, C}$ となる。残りは長さ 4 の欄で、分け目 $k = 1, 2, 3$ をそれぞれ調べればよい。

答えと解説

答えを見る

{S}

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

解説を読む

CYK 法では、長さ 1 の部分文字列から順に、長さ 2、3、4 と $V_{i, j}$ を埋めていく。長さ 2 以上の $w_{i .. j}$ については、すべての分け方 $w_{i .. k} w_{k + 1.. j}$ （ $i \leq k < j$ ）について、 $Y \in V_{i, k}$ 、 $Z \in V_{k + 1, j}$ となる組 $Y Z$ を作り、規則 $X \to Y Z$ があればその $X$ を $V_{i, j}$ に入れる。

規則の右辺に現れる 2 文字の組は $A C (\to S)$ 、 $B B (\to S)$ 、 $A S (\to B)$ 、 $S B (\to C)$ の 4 つだけである。

長さ 1： $A \to a$ 、 $B \to b$ 、 $C \to b$ より
$V_{1, 1} = {A}$ 、 $V_{2, 2} = {A}$ 、 $V_{3, 3} = {B, C}$ 、 $V_{4, 4} = {B, C}$ 。

長さ 2：
- $V_{1, 2}$ ： $V_{1, 1} V_{2, 2}$ からできる組は $AA$ だけで、これを右辺にもつ規則はない。よって $V_{1, 2} = \emptyset$ 。
- $V_{2, 3}$ ： $V_{2, 2} V_{3, 3}$ からできる組は $A B$ , $A C$ 。 $A C$ から $S$ が得られるので $V_{2, 3} = {S}$ 。
- $V_{3, 4}$ ： $V_{3, 3} V_{4, 4}$ からできる組は $B B$ , $B C$ , $C B$ , $C C$ 。 $B B$ から $S$ が得られるので $V_{3, 4} = {S}$ 。

長さ 3：
- $V_{1, 3}$ ：分け方 $k = 1$ では $V_{1, 1} V_{2, 3}$ から $A S$ ができ、 $B$ が得られる。 $k = 2$ では $V_{1, 2} = \emptyset$ なので何も得られない。よって $V_{1, 3} = {B}$ 。
- $V_{2, 4}$ ： $k = 2$ では $V_{2, 2} V_{3, 4}$ から $A S$ ができ、 $B$ が得られる。 $k = 3$ では $V_{2, 3} V_{4, 4}$ から $S B$ , $S C$ ができ、 $S B$ から $C$ が得られる。よって $V_{2, 4} = {B, C}$ 。

長さ 4：
- $k = 1$ ： $V_{1, 1} V_{2, 4}$ から $A B$ , $A C$ ができ、 $A C$ から $S$ が得られる。
- $k = 2$ ： $V_{1, 2} = \emptyset$ なので何も得られない。
- $k = 3$ ： $V_{1, 3} V_{4, 4}$ から $B B$ , $B C$ ができ、 $B B$ から $S$ が得られる。

よって $V_{1, 4} = {S}$ である。

表にまとめると次のようになる（行は部分文字列の長さ、列は開始位置 $i$ ）。

長さ	$i = 1$	$i = 2$	$i = 3$	$i = 4$
1	${A}$	${A}$	${B, C}$	${B, C}$
2	$\emptyset$	${S}$	${S}$
3	${B}$	${B, C}$
4	${S}$

$S \in V_{1, 4}$ なので、 $aabb$ は $G$ で生成される。実際、 $S \Rightarrow A C \Rightarrow a C \Rightarrow a S B \Rightarrow a A C B \Rightarrow aa C B \Rightarrow aab B \Rightarrow aabb$ と導出できる。

答え： $V_{1, 4} = {S}$

別解

文字列は $w = a a b b$ で、 $w_{1} = a, w_{2} = a, w_{3} = b, w_{4} = b$ である。

【長さ1】
$A \to a$ より $V_{1, 1} = V_{2, 2} = {A}$ 。
$B \to b$ 、 $C \to b$ より $V_{3, 3} = V_{4, 4} = {B, C}$ 。

【長さ2】
- $V_{1, 2}$ ： $V_{1, 1} V_{2, 2} = {AA}$ 。右辺が $AA$ の規則はないので $\emptyset$ 。
- $V_{2, 3}$ ： ${A} {B, C} = {A B, A C}$ 。 $S \to A C$ より ${S}$ 。
- $V_{3, 4}$ ： ${B, C} {B, C} = {B B, B C, C B, C C}$ 。 $S \to B B$ より ${S}$ 。

【長さ3】
- $V_{1, 3}$ ：分割 $(1, 1) + (2, 3)$ では ${A} {S} = {A S}$ となり、 $B \to A S$ より $B$ 。分割 $(1, 2) + (3, 3)$ では $V_{1, 2} = \emptyset$ なので何も得られない。よって ${B}$ 。
- $V_{2, 4}$ ：分割 $(2, 2) + (3, 4)$ では ${A} {S} = {A S}$ となり、 $B$ を得る。分割 $(2, 3) + (4, 4)$ では ${S} {B, C} = {S B, S C}$ となり、 $C \to S B$ より $C$ を得る。よって ${B, C}$ 。

【長さ4】
- 分割 $(1, 1) + (2, 4)$ ： ${A} {B, C} = {A B, A C}$ 。 $S \to A C$ より $S$ 。
- 分割 $(1, 2) + (3, 4)$ ： $V_{1, 2} = \emptyset$ なので何も得られない。
- 分割 $(1, 3) + (4, 4)$ ： ${B} {B, C} = {B B, B C}$ 。 $S \to B B$ より $S$ 。

よって $V_{1, 4} = {S}$ 。

検算： $S \Rightarrow B B \Rightarrow A S B \Rightarrow a S B \Rightarrow a A C B \Rightarrow aa C B \Rightarrow aab B \Rightarrow aabb$ と導出できるので、 $S \in V_{1, 4}$ と整合する。したがって $aabb \in L (G)$ である。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題