九州大学 システム情報科学府 情報理工学専攻 2018年8月実施 オートマトンと言語
Author
Zero
Description
【問１】
以下の状態遷移図を持つ非決定性有限オートマトン に対し、次の各問いに答えよ。
ただし、, , , , は、それぞれ状態の集合、アルファベット、遷移関数、初期状態、最終状態の集合を表す。
(1) が受理する長さ 4 の文字列をすべて列挙せよ。
(2) が受理する言語 に含まれる文字列を説明せよ。
(3) を受理する状態数最小の決定性有限オートマトンの状態遷移図を与えよ。
(4) 文字 で始まり文字 で終わる 上の文字列の集合を言語 とする。
言語 を受理する状態数最小の決定性有限オートマトンの状態遷移図を与えよ。
【問２】
1+2+3 や 4+4−10 のように数の加減算を行う式を扱える、次の文脈自由文法 を考える。
文法 の終端記号は 、非終端記号は 、開始記号は であり、生成規則は次の通りである。
開始記号 から生成規則に従った書換えにより導出できる文字列が、 によって生成される文字列である。
例えば は文字列 4+4−10 を次の導出木により生成する。
次の各問い (1), (2) に答えよ。
(1) 次の各文字列は によって生成されるか。されるならば導出木を与え、されないならば理由を説明せよ。
- (a) 5+13+9
- (b) 25
- () 空文字列
- (d) -4+15
(2) は 05+3-0007 のように個々の数を表す部分の先頭に不要な 0 が付いた文字列も生成してしまう。
このような文字列が生成されないように修正した文法 を考える。
文法 の終端記号は 、非終端記号は 、開始記号は であり、生成規則は次の通りである。
ただし は空文字を表す。
が意図通りになるよう空欄 , , を埋めよ。
ただし により生成される文字列のうち、排除したい文字列以外は、すべて により生成されるようにすること。
また他の数字が直後に続かない単独の 0 が現れることは許すものとする。
は例えば 0 や 1+301 や 0+0-203 を生成するが、00 や 1+0301 は生成しない。
Kai
【問１】
(1)
(2)
が連続しない文字列
(3)
(4)
【問１】
(1)
(a)
(b)
生成されない。生成規則に空文字列を終端記号として導出するものが存在しない。
(d)
生成されない。文頭は最終的に非終端記号 から導出されるが、 から「-」は導出されない。
(2)
または