Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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} であり,入力を1つ遅らせて出力するミーリー機械を書け.
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} ,. L={ω|ω∊Σ
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


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

Similar presentations


Ads by Google