解答例

学籍番号
学年
第 3 章字句解析(1)
レポート課題
年
氏名
(4/27〆切)
解答例
1. 正規表現 a(ε|b)(c|d)* を受理する非決定性有限オートマトンを描け。(p.41 3.2 節)
NFA
ε
解答の一例
ε
ε
ε
ε
ε
ε
c
ε
a
ε
ε
b
d
ε
2. 下図の非決定性有限オートマトンと等価な決定性有限オートマトンを描け。(p.44 3.3 節)
DFA
NFA
1
1
q0
0
ε
q2
1
1
qF
1
q0,1
1
1
q2
0
q2,F
0
q1
0
NFA
DFA
QN
ε-closure
goto (q, 0)
goto (q, 1)
QD
ε-closure
goto (q, 0)
goto (q, 1)
q0
q0, q1
φ
q2
q0, q1
q0, q1
φ
q2
q1
q1
φ
q2
q2
q2
q0, q1
q2, qＦ
q2
q2
q0, q1
q2, qＦ
q2, qＦ
q2, qＦ
q0, q1
q2, qＦ
qF
qF
φ
φ

Download Report