形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.

Presentation on theme: "形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅."— Presentation transcript:

1 形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅

2 [1] 正規表現 (1*+01*0)* について以下に答えよ． (1) 正規表現に対応するε-NFA の状態遷移図を書け．
1* と　01*0 ε 1*+01*0 ε (1*+01*0)* 1 ε ε 1 S0 S2 S3 S1 ε ε

3 (2) ε-NFAの状態遷移関数表δε-NFA を書け.
1 S1 ε 1 ε S0 S2 S3 ε

4 (3) δε-NFA を，NFAの状態遷移関数表δNFAへ変換せよ
1 S1 ε 1 ε S0 S2 S3 ε ｛S0, S1, S3} ε閉包 ｛S2} ｛S2, -, -} ｛S2} * ｛S0, S1, S3} ｛-, S1, -} ｛S2, -, -} ｛S2} ｛S0, S1, S3} ｛-, S1, -} ｛S0, S1, S3} ｛S3} ｛S2} ｛S2} ｛S2, -, -} ｛S2} ｛S0, S1, S3} ｛-, S1, -}

5 (4) δNFA を，DFAの状態遷移関数表δDFAへ変換せよ．
* ｛S2} ｛S0, S1, S3} [S0] [S2] * [S0 S1 S3] ｛S2} ｛S0, S1, S3} [S2] [S0 S1 S3] [S2] ｛S0, S1, S3} ｛S2} * [S0 S1 S3] [S2] [S0 S1 S3] ｛S2} ｛S0, S1, S3} NFAの受理状態（S0）を含むものが DFAの受理状態

6 (5) 変換されたDFAの状態遷移図を書け．
1 S0 S0S1S3 S2 [S0] [S2] * [S0 S1 S3] [S2] [S0 S1 S3] [S2] * [S0 S1 S3] [S2] [S0 S1 S3]

7 [2] 入力と出力のアルファベットがともに Σ={a, b, c} であり，入力を１つ遅らせて出力するミーリー機械を書け．
a/a a ε a 1 b/a a/c b a/b c/a b/c c b c c/b b/b c/c

8 [3]次の言語を受理するDFAの状態遷移図を記述せよ．. アルファベット Σ={0, 1} ，. Ｌ={ω|ω∊Σ
Even Odd 1 1 1

9 [4] 次のDFAが受理する言語を正規表現で表せ． ただし，線形再帰方程式を使って解くこと．
S0 = ε + S0 0 + S11 + S21 ① S1 = S01 ② S2 = S10 + S20 ③ S2 = S010 + S20 ③←② ④ ④←⑤ S2 = (ε + S21) (0+11)* 10 + S20 　 = (0+11)* 　S2(1(0+11)*10+0) S0 = ε + S00 + S011 + S21 = (ε + S21) + S0(0+11) ①←② s t 線形回帰方程式を解いて S2 = (0+11)*10 (1(0+11)*10+0)* S0 = (ε + S21) (0+11)* 線形回帰方程式を解いて ⑤

10