编译原理-词法分析 课后习题+笔记

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

p78 3.3.2

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

1. a(a|b)*a
2. ((ε|a)b*)*
3. (a|b)*a(a|b)(a|b)
4. a*ba*ba*ba*
5. !! (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个元音的所有小写字母串，这些中按顺序出现。

Answer

want -> other* a (other|a)* e (other|e)* i (other|i)* o (other|o)* u (other|u)*
other -> [bcdfghjklmnpqrstvwxyz]

知识点（正则定义）

p86 3.4.1

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

1. a(a|b)*a
2. ((ε|a)b*)*
3. (a|b)*a(a|b)(a|b)
4. a*ba*ba*ba*

Answer

1. NFA:

   

   DFA:

   NFA	DFA	a	b
   {0}	A	B
   {1,2,3,5,8}	B	C	D
   {2,3,4,5,7,8,9}	C	C	D
   {2,3,5,6,7,8}	D	C	D

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

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

   

   NFA	DFA	a	b
   {0,1,2,4,7}	A	B	C
   {1,2,3,4,6,7}	B	B	C
   {1,2,4,5,6,7}	C	B	C

3. (a|b)*a(a|b)(a|b)

   NFA:

   

   DFA:

   NFA	DFA	a	b
   {0,1,2,4,7}	A	B	C
   {1,2,3,4,6,7,8,9,11}	B	D	E
   {1,2,4,5,6,7}	C	B	C
   {1,2,3,4,6,7,8,9,10,11,13,14,16}	D	F	G
   {1,2,4,5,6,7,12,13,14,16}	E	H	I
   {1,2,3,4,6,7,8,9,10,11,13,14,15,16,18}	F	F	G
   {1,2,4,5,6,7,12,13,14,16,17,18}	G	H	I
   {1,2,3,4,6,7,8,9,11,15,18}	H	D	E
   {1,2,4,5,6,7,17,18}	I	B	C

​
​

最少状态的 DFA(状态转换图):

合并不可区分的状态 A 和 C

​

​

4. a*ba*ba*ba*

   

知识点（NFA ，DFA ）

• FA的表示：转换图(Transition Graph）
• 最长子串匹配原则(LongestString MatchingPrinciple)
• DFA
• NFA
  
• 转换表 (Transition table) 表示法（有ε边）
  

解答步骤：正则表达式->NFA -> DFA -> 最少状态的 DFA（状态转换图）

• 正则表达式->带ε边的NFA
  

• NFA->DFA（子集构造法）
  注意新建的NFA状态集合中经过一个a/b边还能接着走ε边
  起始集合是起始状态的ε闭包
  
• DFA -> 最少状态的 DFA（状态转换图）

1. 初始划分为 {非终态}，{终态}
2. 若经过a/b边，到达的状态处于同一集合（不一定是自己集合），则不分开，否则分开。直到不能再分，得到最小DFA
   

p96 3.6.4 找出其标号为 aabb 的至少两条路径，越短越好，这个 NFA 接受 aabb 吗？

注： 本题对书上的目作了一些修改，原是找出所有标号为aabb的路径，本题只要求找出至少两条最短路径。

Answer

0-1-0-1-2-3
0-3-0-1-2-3

知识点

p96 3.6.5

给出如下练习中的 NFA的转换表

Answer

与NFA到DFA转换不同，没有ε边

知识点

p105 3.7.1

将下列图中的NFA转换为 DFA

Answer

Transition table

DFA

知识点

NFA->DFA（子集构造法）