九州大学 システム情報科学府 情報理工学専攻 2019年8月実施 オートマトンと言語

Author

Casablanca

Description

【問１】

決定性有限オートマトン を考える． ただし，, , , , はそれぞれ の状態集合，アルファベット，遷移関数，初期状態，最終状態の集合を表す． , , であり， に対し である． ここで は記号 に対応する整数であり，, , , である． 非負の整数 と正の整数 に対し， は を で割ったときの余りを表す． たとえば となる．次の各問いに答えよ．

(1) の状態遷移図を与えよ．

(2) 決定性有限オートマトン は， と同じ状態集合，アルファベット，遷移関数，初期状態を持つ． と等価な決定性有限オートマトンの最小状態数が であるとき，最終状態の集合 の例をひとつ与えよ．

(3) 上の文字列 に対して，

とする． かつ となる のみを受理する決定性有限オートマトン を考える． ただし， の状態集合を , 初期状態を , 最終状態の集合を とする． また，各状態は次のような文字列に対応する．

• は を満たす文字列 に対応．
• は かつ を満たす文字列 に対応．
• は かつ を満たす文字列 に対応．
• は かつ を満たす文字列 に対応．
• は かつ を満たす文字列 に対応．

の状態遷移図を与えよ．

【問２】

アルファベット 上の文字列 に対し， の長さを と表す． また， に対して は の 番目の文字を表す． の逆文字列を と表す． を満たす 上の文字列 と に対して， とする． 文字列 に対し， を満たす文字列 が存在するとき， を の部分文字列という． は に含まれない文字とする． 次の各言語を考える．

これらの言語はすべて文脈自由言語である．例えば，言語 は以下の生成規則を持つ文脈自由文法によって生成される．

ただし， は空文字列を表す．

次の問いに答えよ．

(1) 言語 を生成する文脈自由文法の生成規則を与えよ．ただし，非終端記号を とし，開始記号を とする．

(2) 言語 を生成する文脈自由文法の生成規則を与えよ．ただし，非終端記号を とし，開始記号を とする．

(3) 言語 を生成する文脈自由文法の生成規則を与えよ．ただし，非終端記号を とし，開始記号を とする．

(4) 言語 を生成する文脈自由文法の生成規則を与えよ．ただし，非終端記号を とし，開始記号を とする．

Kai

【問１】

(1)

(2)

(3)

【問２】

(1)

(2)

(3)

(4)