编译原理第三章自动机基础_习题

1、第第3 3章章 习题解答：习题解答：【习题【习题3.23.2】P64_7(1) P64_7(1) 构造构造确定自动机确定自动机 DFA:DFA: e=1(0|1) e=1(0|1)* *101 101 +01 11-1 101 e=(a|b) e=(a|b)* *(aa|bb)(a|b)(aa|bb)(a|b)* *+a ab-a aa ab bb ba ab bA1b a+DFA 变换表变换表DFA 状态图状态图A AB BC CD DE E+-aaabbbbabaE1,3,4D1,2,4E1,3,4D1,2,4E1,3,4B1,2C1,3D1,2,4C1,3B1,2D1,2,4E1,3,4

2、C1,3B1,2-确确 定定 化化第第3 3章章 习题解答：习题解答：【习题】构造一个【习题】构造一个 DFA,DFA,它接收它接收=0,1=0,1上所有满足如下条上所有满足如下条件的字符串：件的字符串：每一个每一个1 1都有都有0 0直接跟在右边。直接跟在右边。【解】【解】+01 1-0 01-0+-010或或【习题【习题3.43.4】给定正规语言，构造有限自动机：】给定正规语言，构造有限自动机： A= a A= an n,ba,ban n |n0 |n0 【解】【解】+-baa-+-baa-第第3 3章章 习题解答：习题解答：【习题【习题3.53.5】 把下述把下述 NFA NFA 转换为

3、转换为 DFA:DFA:ab bab b+ +- -FA1:FA1:ab bab b+ +- -FA2:FA2:ab b+ +- -DFA2:DFA2:A AB BA1ba+ +B2,3B2,3B2,3- -aab b+ +- -DFA1:DFA1:A AB BC Cb bC2,3B2C2,3B2C2,3B2- -A1ba+ +第第3 3章章 习题解答习题解答4 4：【习题【习题3.53.5】 消除消除 NFA NFA 的的 边边：+a- ab b-+b ba a b b a aFA3:FA3:FA4:FA4:【算法】【算法】 逆序删逆序删 边边, ,并补充并补充新新边。边。 闭路合而为一；闭

4、路合而为一； 标记隐含初态和终态标记隐含初态和终态；+-ab ba aDFA1-+b ba ab b a aa ab b-+a aa ab bb ba aDFA2无用无用状态状态第第3 3章章 习题解答：习题解答：【习题【习题3.83.8】已知符号串集合，构造正规式、自动机和正】已知符号串集合，构造正规式、自动机和正规文法：规文法：A= A= ,a,an n,ba,ban n|n1 |n1 【解】【解】 正规式正规式: : e=e= |a|a+ +|ba|ba+ + 或或 e=e=a a* *|ba|ba+ + 自动机自动机 DFA: DFA: aa a+ +- -1 12 2b b- -3

5、3a 正规文法正规文法: : S SA AB BS - aA|bB|S - aA|bB| A - aA|A - aA| B - aAB - aA【习题【习题3.93.9】已知自动机】已知自动机DFA:DFA:ab bb bc cc cb bb b- -+ +- - 扩展扩展DFA(DFA(加入结束标记加入结束标记#),#),构造压缩变换表；构造压缩变换表； 根据实现算法，写出识别根据实现算法，写出识别 abbc#abbc#的过程。的过程。 输入串输入串 abbc# abbc# 识别过程：识别过程：第第3 3章章 习题解答：习题解答：【解】【解】 扩展扩展DFA:DFA:压缩变换表压缩变换表 nonob ba a nonob b索引表索引表 nonoc cb b nonoc cb b nonookok# #1 1备注备注变换变换剩余剩余chchstatestateab bb bc cc cb bb