1、第 4 章 词法分析1.构造下列正规式相应的DFA.（） 1(0|1) *101答案：1) 先构造 NFA：2)将NFA 确定化 :Q 0 1X X A AA A A A A,B BA,B B A,C C A,B BA,C C A A A,B,Y YA,B,Y Y A,C C A,B B3) DFA:2. 已知NFA （ x,y,z,0,1,M,x,z），其中：M(x,0)=z，M(y,0)=x,y ，,M(z,0)=x,z，M(x,1)=x，M(y,1)= ，M(z,1)=y，构造相应的DFA。答案：1) 根据题中映射，得如下 NFA 转换矩阵：0 1x z xy x,y z x,z y2)
2、 转成 NFA（这步可省）：11 100/1AX B 01 ASBCYC3) 确定化： Q 0 1x X z A x Xz A x,z B y Cx,z B x,z B x,y Ey C x,y E x,y E x,y,z F x Xx,y,z F x,y,z F x,y E4. 将下图的（a）和（b）分别确定化和最小化：（a ） 确定化： Q a b0 0 0,1 1 1 20,1 1 0,1 1 1 21 2 0 0 最小化：0 0,1 2因为：0,1 a=1 0,1b=2 不能拆分1 0,1 20,1 二状态合并，得（b） 因为自动机（b）已确定化，所以只做最小化：0 1,2,3,4,5
3、 0因为 4a=0 1,2,3,5a=1,2,3, 51 1,2,3,5 4 0因为1,5b=4 2,3b=2,32 1, 5 2,3 4 0因为 2a=1 3a=33 1, 5 2 3 4 0因为 1, 5a=1,5 1, 5b=4 不能拆分4 1, 5 2 3 4 0将 1, 5合并得：5.构造一个DFA，它接收=0,1上所有满足如下条件的字符串：每个1 都有0 直接跟在右边。并给出该语言的正规式。答案：1)按题意相应的正规表达式可为(0 | 10)*， 构造相应的DFA ：2)将DFA转成右线性文法：S-A|A-0A|0|1BB-0A|08.给出下述文法所对应的正规式：S0A|1BA1S
4、|1B0S|0答案：将A、B 产生式的右部代入S 中,得：S=01S|01|10S|10=（01|10）S| 01|10所以：S= (01|10)* |01|1010.构造下述文法GS的自动机：S-A0A-A0|S1|0该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？答案：1) 将题中左线性文法转换为自动机：因为是左线性文法，要增加一开始状态X，开始符号S成终结状态：2) 该自动机为 NFA，确定化： Q 0 1x X A A A A A,S B A,S B A,S B A A3) 该自动机表达的语言用正规式表示为：00(0|10)*， 或：以 00 开头， 0 结尾，中
5、间若有 1，则 1 后一定跟 0。附加题：已有 NFA M=（S，A ，B ，F，0,1,f,S,F）,状态图如下图所示，1 将此 NFA 转化成规范 DFA； 2 转化成正规文法。 3. 列出它拒绝接受的 2 个字符串（不同字符开头） 答案：1. 确定化：Q 0 1S S A,F A A,F A A,F A A,B BA,B B A,F A A,B,F CA,B,F C A,F A A,B,F C此 DFA 已为最小化的 DFA2. 转化成右线性的正规文法S-0A|0A-0A|0|1BB-0A|0|1C|1C-0A|0|1C|13. 列出它拒绝接受的 2 个字符串（不同字符开头）1)10000 (所有 1 开头的串)2)00000(所有 0 结尾的串)
