编译原理

2023-10-14 06:42| 来源: 网络整理| 查看: 265

词法分析

来源：龙书（厚），南大课后作业

p78 3.3.2

试描述下列正则表达式定义的语言：

a(a|b)*a((ε|a)b*)*(a|b)*a(a|b)(a|b)a*ba*ba*ba*!! (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)* Answer

(a) 由 a 开头并结尾的由 a 和 b 构成的字符串 (b) 由 a 和 b 构成的字符串 © 倒数第三位为 a 的由 a 和 b 构成的字符串 (d) 仅含 3 个 b 的由 a 和 b 构成的字符串 (e) 含有偶数个 a 和偶数个 b 的由 a 和 b 构成的字符串

注意：请准确描述语言的性质而不是列举满足正则表达式串

知识点（正则表达式）

运算的优先级：* > 连接 > |，如(a) | ((b)©) = a | bc

在这里插入图片描述

p79 3.3.5

试写出下列语言的正则定义：（1）包含 5个元音的所有小写字母串，这些中按顺序出现。

在这里插入图片描述

p86 3.4.1

给出识别练习 3.3.2 （厚书）中各个正则表达式所描述的语言状态转换图。

a(a|b)*a((ε|a)b*)*(a|b)*a(a|b)(a|b)a*ba*ba*ba* Answer

NFA:

3 4 1-1-nfa

DFA:

NFADFAab{0}AB{1,2,3,5,8}BCD{2,3,4,5,7,8,9}CCD{2,3,5,6,7,8}DCD

最少状态的 DFA(状态转换图): 3 4 1-1-dfa 合并不可区分的状态 B 和 D 3 4 1-1

((ε|a)b*)* 注意初始的NFA集合是开始状态0的ε闭包，不是只有0

3 4 1-2

NFADFAab{0,1,2,4,7}ABC{1,2,3,4,6,7}BBC{1,2,4,5,6,7}CBC

(a|b)*a(a|b)(a|b)

NFA:

3 4 1-3-nfa

DFA:

NFADFAab{0,1,2,4,7}ABC{1,2,3,4,6,7,8,9,11}BDE{1,2,4,5,6,7}CBC{1,2,3,4,6,7,8,9,10,11,13,14,16}DFG{1,2,4,5,6,7,12,13,14,16}EHI{1,2,3,4,6,7,8,9,10,11,13,14,15,16,18}FFG{1,2,4,5,6,7,12,13,14,16,17,18}GHI{1,2,3,4,6,7,8,9,11,15,18}HDE{1,2,4,5,6,7,17,18}IBC

最少状态的 DFA(状态转换图): 合并不可区分的状态 A 和 C

3 4 1-3