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

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

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

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

全体の欄 $V_{1, 4}$ として正しいものを、次のア〜エから 1 つ選べ。

ア　 $\emptyset$ （空集合）

イ　 ${S}$

ウ　 ${B}$

エ　 ${S, B}$

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

CYK 法を使います。長さ 1 の部分文字列から順に、各部分文字列を導出できる非終端記号の集合 $V_{i, j}$ を表に埋めていきましょう。

ヒント 2

$V_{i, j}$ には、区切り $k$ （ $i \leq k < j$ ）ごとに $Y \in V_{i, k}$ 、 $Z \in V_{k + 1, j}$ をとり、規則 $X \to Y Z$ があればその $X$ を入れます。使う 2 文字の規則は $S \to A B$ 、 $S \to S C$ 、 $B \to S B$ だけです。

ヒント 3

$V_{1, 1} = {A}$ 、 $V_{2, 2} = {B}$ 、 $V_{3, 3} = {C}$ 、 $V_{4, 4} = {B}$ 、 $V_{1, 2} = {S}$ 、 $V_{2, 3} = V_{3, 4} = \emptyset$ 、 $V_{1, 3} = {S}$ 、 $V_{2, 4} = \emptyset$ となります。あとは $V_{1, 4}$ の区切り $k = 1, 2, 3$ を調べましょう。

答えと解説

答えを見る

ウ

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

解説を読む

CYK 法では、長さ $1$ の部分文字列から順に $V_{i, j}$ を埋めていく。長さ $2$ 以上の欄 $V_{i, j}$ は、区切り位置 $k$ （ $i \leq k < j$ ）ごとに $Y \in V_{i, k}$ 、 $Z \in V_{k + 1, j}$ を選び、規則 $X \to Y Z$ があればその $X$ を $V_{i, j}$ に入れる。

使う 2 文字の規則は $S \to A B$ 、 $S \to S C$ 、 $B \to S B$ の 3 つだけである。

長さ 1（規則 $X \to$ 終端記号を使う）
$w_{1} = a, w_{2} = b, w_{3} = c, w_{4} = b$ より
$V_{1, 1} = {A}, V_{2, 2} = {B}, V_{3, 3} = {C}, V_{4, 4} = {B} .$

長さ 2
- $V_{1, 2}$ （ $ab$ ）： $V_{1, 1} V_{2, 2}$ から並び $A B$ 。 $S \to A B$ があるので $V_{1, 2} = {S}$ 。
- $V_{2, 3}$ （ $b c$ ）：並び $B C$ 。右辺が $B C$ の規則はないので $V_{2, 3} = \emptyset$ 。
- $V_{3, 4}$ （ $c b$ ）：並び $C B$ 。該当する規則はないので $V_{3, 4} = \emptyset$ 。

長さ 3
- $V_{1, 3}$ （ $ab c$ ）： $k = 1$ のとき $V_{1, 1} V_{2, 3}$ は $V_{2, 3} = \emptyset$ なので何も得られない。 $k = 2$ のとき $V_{1, 2} V_{3, 3}$ から並び $S C$ 。 $S \to S C$ があるので $S$ 。よって $V_{1, 3} = {S}$ 。
- $V_{2, 4}$ （ $b c b$ ）： $k = 2$ のとき $V_{2, 2} V_{3, 4}$ は $V_{3, 4} = \emptyset$ 、 $k = 3$ のとき $V_{2, 3} V_{4, 4}$ は $V_{2, 3} = \emptyset$ なので、 $V_{2, 4} = \emptyset$ 。

長さ 4
- $k = 1$ ： $V_{1, 1} V_{2, 4}$ は $V_{2, 4} = \emptyset$ なので何も得られない。
- $k = 2$ ： $V_{1, 2} V_{3, 4}$ は $V_{3, 4} = \emptyset$ なので何も得られない。
- $k = 3$ ： $V_{1, 3} V_{4, 4}$ から並び $S B$ 。 $B \to S B$ があるので $B$ 。右辺が $S B$ の規則はこれだけである。

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

表にまとめると次のようになる（上の行ほど長い部分文字列）。

長さ
4	${B}$
3	${S}$	$\emptyset$
2	${S}$	$\emptyset$	$\emptyset$
1	${A}$	${B}$	${C}$	${B}$
文字	$a$	$b$	$c$	$b$

実際に $B \Rightarrow S B \Rightarrow S C B \Rightarrow A B C B \Rightarrow ab c b$ と導出できる。一方、 $S \in / V_{1, 4}$ なので、 $w = ab c b$ は $G$ では生成されない。

答えはウ。

別解

CYK 法で表を埋める。

長さ 1
- $V_{1, 1} = {A}$ （ $A \to a$ ）
- $V_{2, 2} = {B}$ （ $B \to b$ ）
- $V_{3, 3} = {C}$ （ $C \to c$ ）
- $V_{4, 4} = {B}$ （ $B \to b$ ）

長さ 2
- $V_{1, 2}$ ： $A B$ より $S \to A B$ が使えるので ${S}$
- $V_{2, 3}$ ： $B C$ を右辺にもつ規則はないので $\emptyset$
- $V_{3, 4}$ ： $C B$ を右辺にもつ規則はないので $\emptyset$

長さ 3
- $V_{1, 3}$ ：
- 分割 $1∣23$ ： $V_{2, 3} = \emptyset$ なので不可
- 分割 $12∣3$ ： $V_{1, 2} = {S}$ 、 $V_{3, 3} = {C}$ より $S C$ から $S \to S C$ が使える
- よって ${S}$
- $V_{2, 4}$ ：
- 分割 $2∣34$ ： $V_{3, 4} = \emptyset$ なので不可
- 分割 $23∣4$ ： $V_{2, 3} = \emptyset$ なので不可
- よって $\emptyset$

長さ 4
- $V_{1, 4}$ ：
- 分割 $1∣234$ ： $V_{2, 4} = \emptyset$ なので不可
- 分割 $12∣34$ ： $V_{3, 4} = \emptyset$ なので不可
- 分割 $123∣4$ ： $V_{1, 3} = {S}$ 、 $V_{4, 4} = {B}$ より $S B$ から $B \to S B$ が使える
- $S \to S C$ は $V_{4, 4}$ に $C$ が含まれないので使えない
- $S \to A B$ は $V_{1, 1} = {A}$ と $V_{2, 4} = \emptyset$ の組になるので使えない
- よって $V_{1, 4} = {B}$

確認： $B \Rightarrow S B \Rightarrow S C B \Rightarrow A B C B \Rightarrow ab c b$ と導出でき、 $B$ は $w$ を導出できる。一方 $S$ は含まれないので $w \in / L (G)$ である。

選択肢の検討：
- ア： $B$ が入るので誤り
- イ： $S$ は入らないので誤り
- ウ：正しい
- エ： $S$ が入らないので誤り

答えはウ。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題