Download presentation
Presentation is loading. Please wait.
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)* 線形回帰方程式を解いて ⑤
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.