形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅
[1] 正規表現 (1*+01*0)* について以下に答えよ． (1) 正規表現に対応するε-NFA の状態遷移図を書け． 1* と 01*0 ε 1*+01*0 ε (1*+01*0)* 1 ε ε 1 S0 S2 S3 S1 ε ε
(2) ε-NFAの状態遷移関数表δε-NFA を書け. 1 S1 ε 1 ε S0 S2 S3 ε
(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, -}
(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の受理状態
(5) 変換されたDFAの状態遷移図を書け． 1 S0 S0S1S3 S2 [S0] [S2] * [S0 S1 S3] [S2] [S0 S1 S3] [S2] * [S0 S1 S3] [S2] [S0 S1 S3]
[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
[3]次の言語を受理するDFAの状態遷移図を記述せよ．. アルファベット Σ={0, 1} ，. Ｌ={ω|ω∊Σ Even Odd 1 1 1
[4] 次のDFAが受理する言語を正規表現で表せ． ただし，線形再帰方程式を使って解くこと． S0 = ε + S0 0 + S11 + S21 ① S1 = S01 ② S2 = S10 + S20 ③ S2 = S010 + S20 ③←② ④ ④←⑤ S2 = (ε + S21) (0+11)* 10 + S20 = (0+11)*10 + 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)* 線形回帰方程式を解いて ⑤