第4 章作业答案.doc

第4章 词法分析1.构造下列正规式相应的DFA.（） 1(0|1)*101答案：1) 先构造NFA：11100/1AXBYC2)将NFA 确定化:Q 01X XA AA AA AA,B BA,B BA,C CA,B BA,C CA AA,B,Y YA,B,Y Y A,C CA,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转换矩阵：01xzxyx,yzx,zy2) 转成NFA（这步可省）：3) 确定化： Q 01x Xz Ax Xz Ax,z By Cx,z Bx,z Bx,y Ey Cx,y Ex,y Ex,y,z Fx Xx,y,z Fx,y,z Fx,y E4. 将下图的（a）和（b）分别确定化和最小化：（a） 确定化： Q ab0 00,1 11 20,1 10,1 11 21 20 0最小化：0 0,1 2因为：0,1a=1 0,1b=2 不能拆分1 0,1 20,1二状态合并，得（b） 因为自动机（b）已确定化，所以只做最小化：0 1,2,3,4,5 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|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 01x XA AA AA,S BA,S BA,S BA A3) 该自动机表达的语言用正规式表示为：00(0|10)*， 或：以00开头，0结尾，中间若有1，则1后一定跟0。附加题：已有NFA M=（S，A，B，F，0,1,f,S,F）,状态图如下图所示，1 将此NFA转化成规范DFA； 2 转化成正规文法。 3. 列出它拒绝接受的2个字符串（不同字符开头） 答案：1. 确定化： Q 01S SA,F AA,F AA,F AA,B BA,B BA,F AA,B,F CA,B,F CA,F AA,B,F C此DFA已为最小化的DFA2. 转化成右线性的正规文法S-0A|0A-0A|0|1BB-0A|0|1