第3章 习题
3-1 试构造一右线性文法，使得它与如下的文法等价
S→AB A→UT U→aU|a D→bT|b
B→cB|c
并根据所得的右线性文法，构造出相应的状态转换图。
3-2 对于如题图3-2所示的状态转换图
00D01A0B01C11F0E1题图3-2 (1) 写出相应的右线性文法； (2) 指出它接受的最短输入串；
(3) 任意列出它接受的另外4个输入串； (4) 任意列出它拒绝接受的4个输入串。
3-3 对于如下的状态转换矩阵：
a b a b SA S SA BA A B A B A BB B BB B(ⅰ) 初态:S终态:B(ⅲ) 初态:S终态:Ba b a b SAA B SA SC A A C B B B C B B CCC C CC C(ⅳ) 初态:S终态:C题图3-3
(ⅱ) 初态:S终态:A,C(1) 分别画出相应的状态转换图； (2) 写出相应的3型文法；
(3) 用自然语言描述它们所识别的输入串的特征。
3-4 将如下的NFA确定化和最小化：
aSaAbbBa(1)bSaAaC(2) aaBSaAbBb(3)bBaAaCa, b(4)a题图3-4
3-5 将如题图3-5所示的具有ε动作的NFA确定化。
SaABbCεεc(1)SbRaaZabεXbbUaY(2)题图3-5 具有ε动作的NFA
3-6 设有文法G[S]：
S→aA A→aA|bB B→bB|cC|c 试用正规式描述它所产生的语言。
3-7 分别构造与如下正规式相应的NFA。
(1) ((0* |1)(1* 0))* (2) b|a(aa*b)*b
C→cC|c
蒋立源编译原理第三版第三章习题与答案
