第4-章作业答案

第4章词法分析1.构造下列正规式相应的DFA.（１）1(0|1)*101答案：1)先构造NFA：2)将NFA确定化:∑Q01[X]X[A]A[A]A[A]A[A,B]B[A,B]B[A,C]C[A,B]B[A,C]C[A]A[A,B,Y]Y[A,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转换矩阵：01xzxyx,yzx,zy2)转成NFA（这步可省）：11100/1AXB0ε1ε10εASBCCCYC3)确定化：∑Q01[x]X[z]A[x]X[z][A][x,z]B[y]C[x,z][B][x,z]B[x,y]E[y]C[x,y]E[x,y]E[x,y,z]F[x]X[x,y,z][F][x,y,z]F[x,y]E4.将下图的（a）和（b）分别确定化和最小化：（a）确定化：∑Qab[0][0][0,1]1[1]2[0,1][1][0,1]1[1]2[1]2[0]0最小化：0{0,1}{2}因为：{0,1}a={1}{0,1}b={2}不能拆分1{0,1}{2}0,1二状态合并，得（b）因为自动机（b）已确定化，所以只做最小化：0{1,2,3,4,5}{0}因为{4}a={0}{1,2,3,5}a={1,2,3,5}1{1,2,3,5}{4}{0}因为{1,5}b={4}{2,3}b={2,3}2{1,5}{2,3}{4}{0}因为{2}a={1}{3}a={3}3{1,5}{2}{3}{4}{0}因为{1,5}a={1,5}{1,5}b={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.给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|0答案：将A、B产生式的右部代入S中,得：S=01S|01|10S|10=（01|10）S|01|10所以：S=(01|10)*|01|1010.构造下述文法G[S]的自动机：S-A0A-A0|S1|0该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？答案：1)将题中左线性文法转换为自动机：因为是左线性文法，要增加一开始状态X，开始符号S成终结状态：2)该自动机为NFA，确定化：∑Q01[x]X[A]A[A]A[A,S]B[A,S][B][A,S]B[A]A3)该自动机表达的语言用正规式表示为：00(0|10)*，或：以00开头，0结尾，中间若有1，则1后一定跟0。附加题：已有NFAM=（{S，A，B，F}，{0,1},f,{S},{F}）,状态图如下图所示，1．将此NFA转化成规范DFA；2．转化成正规文法。3.列出它拒绝接受的2个字符串（不同字符开头）答案：1.确定化：∑Q01[S]S[A,F]A[A,F][A][A,F]A[A,B]B[A,B]B[A,F]A[A,B,F]C[A,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结尾的串)