1、写出非负整数的正规表达式。例子：1234或0或10230123或－123非法<非负整数>→<数字>|<非0数字><整数><整数>→<数字>|<整数><数字><数字>→0|1|2|…|9<非0数字>→1|2|…|92、写出以非5数字为开头的所有非负整数之集的正规表达式。例子：1234或0或10230123或5123非法解：D=1|2|…|9E=1|2|3|4|6|7|8|9L=0|E(0|D)*8、把下列NDFA转化为DFA:12a3ba+-b12a3ba+-b解：A1设改为A,B,C状态ab+1222,3-2,322,3ABaCba+-aab+12,3-2,32,3A2设改为A,B状态ABa+-b15、写出下面DFA的正规表达式12b3ab+-b4aaa得到确定DFA：ab+1222,3-2,32,32,3,4-2,3,42,32,3,4-2,3,42,32,3,4123ab+-b4aab-最小化DFA：123a+-bab得到正规表达式：13+-aba|b13+-ab(a|b)*结果：ab(a|b)*1、构造下列正则式相应的DA:(1)1(0|1)*101(2)1(1010*|1(010)*1)*0(3)a((a|b)*|ab*a)b(4)b((ab)*|bb)*ab解：1）SZ+-1(0|1)*101SZ+-101121(0|1)*SZ+-10112113εε0SZ+-112113εε04510SZ+-1121131104510010+S113333,433,43,43,53,53,4,Z3-3,4,Z3,43,516+-1211311045000012、已知NDFA=({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:写出状态转换矩阵01+xzxyx,y-zx,zyyx-10z01000+确定自动机：01+xzx-zx,zy-x,zx,zx,yyx,yx,yx,y,zx-x,y,zx,y,zx,yx-1y0A010+z001BC10--1、设有文法G[N]:N→D|NDD→0|1|2|…|9(1)试写出021和4321的最右推导和最左推导。解:(1)021的最左推导：NNDNDDDDD0DD02D021021的最右推导：NNDN1ND1N21D21021解:4321的最左推导：NNDNDDNDDDDDDD4DDD43DD432D43214321的最右推导：NNDN1ND1N21ND21N321D32143213、设有文法G[E]:E→T|E+T|E-TT→F|T*F|T/FF→i|(E)(1)试写出i*i/(i+i*i)的语法树。(2)试写出句型T*F*(T+i)的最右推导。解：(1)i*i/(i+i*i)的语法树：（见下页）(2)最右推导ETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*F*(T+i)ET/FT*FTFiE)(+TE*FTFiTFiii5、对下面的文法G:E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|A|B|∧A→aB→b(1)计算这个文法的每个非终结符的First集和follow集。解：first(E)=first(T)=first(F)=first(P)={(,a,b,∧}first(E’)={+,ε}first(T’)=first(T)∪{ε}={(,a,b,∧,ε}first(F’)={*,ε}follow(E)=follow(E’)∪{}}∪{#}={),#}follow(E’)=follow(E)={),#}follow(T)=first(E’)-ε∪follow(E)∪