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

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

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

終端記号 ${0, 1}$ 、非終端記号 ${S, A, B, C}$ 、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$S \to A C ∣ B S, C \to S B ∣ 1, A \to 0, B \to 1$
文字列 $w = 0011$ の $i$ 文字目を $w_{i}$ とし、 $1 \leq i \leq j \leq 4$ に対して、部分文字列 $w_{i} w_{i + 1} \dots w_{j}$ を生成する非終端記号全体の集合を $X_{i, j}$ とする。CYK 法で $X_{i, j}$ の表を短い部分文字列から順に埋めたとき、全体の欄 $X_{1, 4}$ に入る集合として正しいものを、次のア〜エから 1 つ選べ。

ア　 $\emptyset$ 　　イ　 ${S}$ 　　ウ　 ${C}$ 　　エ　 ${S, C}$

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

CYK 法を使う。長さ 1 の部分文字列の欄から始めて、長さ 2、3、4 の順に $X_{i, j}$ を埋めていく。

ヒント 2

長さ 2 以上の欄では、 $i \leq k < j$ となるすべての $k$ について、 $P \in X_{i, k}$ , $Q \in X_{k + 1, j}$ を満たす組 $P Q$ を作る。規則 $R \to P Q$ があれば、 $R$ を $X_{i, j}$ に入れる。

ヒント 3

長さ 1 の欄は $X_{1, 1} = X_{2, 2} = {A}$ , $X_{3, 3} = X_{4, 4} = {B, C}$ である。長さ 2 の欄は $X_{1, 2} = \emptyset$ , $X_{2, 3} = {S}$ , $X_{3, 4} = \emptyset$ になる。

答えと解説

答えを見る

イ

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

解説を読む

CYK 法では、長さ 1 の部分文字列から順に $X_{i, j}$ を求める。長さ 2 以上の欄は、部分文字列を前後 2 つに分ける分け方をすべて調べる。前半を生成する記号 $P \in X_{i, k}$ と後半を生成する記号 $Q \in X_{k + 1, j}$ について、規則 $R \to P Q$ があれば $R$ を $X_{i, j}$ に入れる（ $i \leq k < j$ ）。

長さ 1（規則 $R \to$ 終端記号を見る）
- $w_{1} = 0$ , $w_{2} = 0$ ： $0$ を生成するのは $A$ だけなので、 $X_{1, 1} = X_{2, 2} = {A}$ 。
- $w_{3} = 1$ , $w_{4} = 1$ ： $1$ を生成するのは $B$ と $C$ なので、 $X_{3, 3} = X_{4, 4} = {B, C}$ 。

長さ 2
- $X_{1, 2}$ ：組は $AA$ だけ。右辺が $AA$ の規則はないので $X_{1, 2} = \emptyset$ 。
- $X_{2, 3}$ ：組は $A B, A C$ 。 $S \to A C$ があるので $X_{2, 3} = {S}$ 。
- $X_{3, 4}$ ：組は $B B, B C, C B, C C$ 。右辺の 2 文字の組は $A C, B S, S B$ しかないので、どれも当てはまらず $X_{3, 4} = \emptyset$ 。

長さ 3
- $X_{1, 3}$ ：分け方 $X_{1, 1} X_{2, 3}$ からは組 $A S$ だけが出るが、該当する規則はない。分け方 $X_{1, 2} X_{3, 3}$ は $X_{1, 2} = \emptyset$ なので何も出ない。よって $X_{1, 3} = \emptyset$ 。
- $X_{2, 4}$ ：分け方 $X_{2, 2} X_{3, 4}$ は $X_{3, 4} = \emptyset$ なので何も出ない。分け方 $X_{2, 3} X_{4, 4}$ からは組 $S B, S C$ が出て、 $C \to S B$ がある。よって $X_{2, 4} = {C}$ 。

長さ 4
- 分け方 $X_{1, 1} X_{2, 4}$ ：組 $A C$ が出て、 $S \to A C$ がある。よって $S$ が入る。
- 分け方 $X_{1, 2} X_{3, 4}$ ：どちらも $\emptyset$ なので何も出ない。
- 分け方 $X_{1, 3} X_{4, 4}$ ： $X_{1, 3} = \emptyset$ なので何も出ない。

したがって $X_{1, 4} = {S}$ である。開始記号 $S$ が全体の欄に入るので、 $w = 0011$ は $G$ で生成される。実際に $S \Rightarrow A C \Rightarrow 0 C \Rightarrow 0 S B \Rightarrow 0 A C B \Rightarrow 00 C B \Rightarrow 001 B \Rightarrow 0011$ と導出でき、結果と一致する。

答えはイである。

別解

w=0011 なので、 $w_{1} = 0, w_{2} = 0, w_{3} = 1, w_{4} = 1$ 。

長さ1:
- $X_{1, 1} = {A}$ 、 $X_{2, 2} = {A}$ ( $A \to 0$ )
- $X_{3, 3} = {B, C}$ 、 $X_{4, 4} = {B, C}$ ( $B \to 1, C \to 1$ )

長さ2:
- $X_{1, 2}$ : 右辺が $AA$ となる規則はないので $\emptyset$
- $X_{2, 3}$ : $A \cdot B$ の規則はなく、 $A \cdot C$ は $S \to A C$ なので ${S}$
- $X_{3, 4}$ : $B B, B C, C B, C C$ を右辺にもつ規則はないので $\emptyset$

長さ3:
- $X_{1, 3}$ : $(X_{1, 1}, X_{2, 3}) = A \cdot S$ は該当なし。 $(X_{1, 2}, X_{3, 3})$ は $\emptyset$ なので $\emptyset$
- $X_{2, 4}$ : $(X_{2, 2}, X_{3, 4})$ は $\emptyset$ 。 $(X_{2, 3}, X_{4, 4}) = S \cdot B$ は $C \to S B$ 、 $S \cdot C$ は該当なし。よって ${C}$

長さ4:
- $(X_{1, 1}, X_{2, 4}) = A \cdot C$ は $S \to A C$ より $S$
- $(X_{1, 2}, X_{3, 4}) = \emptyset$
- $(X_{1, 3}, X_{4, 4}) = \emptyset$

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

検算: 導出 $S \to A C \to 0 C \to 0 S B \to 0 A C B \to 00 C B \to 001 B \to 0011$ が成り立つ。確かに $0011$ は $G$ で生成される。正解はイ。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題