九州大学 システム情報科学府 情報理工学専攻 2017年8月実施 オートマトンと言語
Author
Zero
Description
【問１】
以下の遷移図を持つ非決定性有限オートマトン に対し, 次の各問いに答えよ。ただし, , , , , は, それぞれ状態の集合, アルファベット, 遷移関数, 初期状態, 最終状態の集合を表す。 によって受理される言語を とする。
(1) に含まれる長さ の文字列をすべて列挙せよ。
(2) に含まれる任意の文字列を, 正規表現 を用いて表すことができる。ただし, と はともに 上の文字列である。これらの文字列 と を与えよ。
(3) を 上の文字列とする。以下の つの命題はそれぞれ真であるか偽であるか。真ならば理由を説明し, 偽ならば反例を与えよ。
-
(a) 「 ならば, は の部分文字列ではない。」
-
(b) 「 が の部分文字列でないならば, である。」
(4) を受理する状態数最小の決定性有限オートマトンの遷移図を与えよ。
【問２】
文脈自由文法 , を考える．
ただし，, , , はそれぞれ非終端記号の集合，終端記号の集合，生成規則の集合，開始記号とする.
ここで, , とする．
(1) による文字列 の導出過程を与えよ．
(2) が生成する言語 に含まれる文字列を説明せよ．
(3) が生成する言語 に含まれる文字列を説明せよ．
(4) 言語 を生成する文脈自由文法 の生成規則の集合 を与えよ．ただし, .
Kai
【問１】
(1)
で終わることがない、かつ を連続で含まないことが条件になっているので
(2)
(1) を基に考えると
(3)
(a)
真;
理由：(2) より 上の文字列 は, と表せるので、 の後に連続して がくることがないから。
(b)
偽;
反例：
(4)
上の表から が等しいことがわかる。また、 はどの状態からも遷移先になっていないことが。
よって、遷移表は以下のようになる。
ゆえに、求める状態数最小の決定性有限オートマトン 遷移図は
【問２】
(1)
(2)
(3)
(4)