学籍番号 学年 第 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 φ φ
© Copyright 2025 ExpyDoc
