编译原理第章习习题课|构造下列正规式相应DFA_水平构造

认证主体：魏**（实名认证）

IP属地：广东

下载本文档

1、1.构造正规式的DFA。（1）1(0|1)*1010YXCADBE首先构造NFA：0X11E1DCBA1NFA化为DFA：状态转换表：Q10X AABC BABC BBCD CBC DBCD CBCD CBCE EBC DBCD CBC DBCE EBCDY YBC DBCDY YBCD CBCE E1状态转换图：0110110YABCDE10 初态010ABBCDCCEDCDEYDYCE化简后得：01ABEY1101001C（2）(a|b)*(aa|bb)(a|b)*X12345Yaabbabab NFA化为DFA：QabX 1 21 2 31 2 41 2 31 2 3 5 Y1 2 4

2、1 2 41 2 31 2 4 5 Y1 2 3 5 Y1 2 3 5 Y1 2 4 Y1 2 4 5 Y1 2 3 Y1 2 4 5 Y1 2 4 Y1 2 3 Y1 2 4 5 Y1 2 3 Y1 2 3 5 Y1 2 4 Ya所以，DFA为：X123456ababbabbabaab化简得：1XY2baababab01BCDYXA10（3）（0|11*0）*NFA到DFA：Q10X A Y XB C D AA Y BB C D AC D YA Y BA Y BB C D AA Y BC D YC D YA Y BABYX10100110化简后得；XA10012.将下图确定化和最小化。aa&

3、#222; 0 1 a,b解: 首先取A=-CLOSURE(0)=0, NFA确定化后的状态矩阵为:QabA00,11B0,10,11C10NFA确定化后的DFA为：aaÞABabbC将A,B 合并得:abÞ ACa3.构造一个DFA，它接受=0，1上所有满足如下条件的字符串，每个1都有0直接跟在后边。解：按题意相应的正规表达式是0*(0 | 10)*0* 构造相应的DFA，首先构造NFA为 0 0 03 1 0 X Y 1 02 用子集法确定化II0I1S01X,0,1,3,Y0,1,3,Y21,3,Y0,1,3,Y0,1,3,Y1,3,Y1,3,Y22/21234224

5、b*）*的 NFA为：3a其最简化DFA为：aA2Y1 => X =>bb DFA的状态转换表：abx,1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y由于这两个正规式的最小DFA相同，所以正规式(a|b)*等价于正规式(a*|b*)*。6.设字母表=a,b,给出上的正规式R=b*ab(b|ab)*。（1）试构造状态最小化的DFA M，使得L（M）=L（R）。（2）求右线性文法G，使L（G）=L（M）。解: (1)构造NFA:X123Ybab456abb (2)将其化为DFA,转换矩阵为:QabX,1,2 13 21,2 33 24,5,Y

6、41,2 33 21,2 34,5,Y 46 55,Y 66 55,Y 65,Y 66 55,Y 6123456abbababbba再将其最小化得:XWYabbab（2）对应的右线性文法G=（X,W,Y,a,b,P,X）P: XaW|bX WbY|b yaW|bY|b 文法G单词为：单词-标识符|整数标识符-标识符字母|标识符数字|字母整数-数字|整数数字字母-A|B|C数字|->1|2|3（1）改写文法G为G，使L(G)=L(G)。（2）给出相应的有穷自动机。解：（1）令D代表单词，I代表标识符，Z代表整数，有G（D）：DI | Z IA | B | C | IA | IB | IC

7、| I1 | I2 | I3Z1 | 2 | 3 | Z1 | Z2 | Z3(2) 左线性文法G所对应的有穷自动机为：M=(S,D,I,Z,1,2,3,A,B,C,f,S,D)f: f(S,A)=I, f(S,B)=I, f(S,C)=I f(S,1)=Z f(S,2)=Z f(S,3)=Z f(I,A)=I f(I,B)=I f(I,C)=If(I,1)=I f(I,2)=I f(I,3)=I f(I, )=If(Z,1)=Z f(Z,2)=Z f(Z,3)=Z f(Z, )=D给出下述文法所对应的正规式。S0A|1BA1S|1B0S|0解: 相应的正规式方程组为：S=0A+1B A=1S

9、|bA-> aS 对应的NFA为： M=(S,A,D,a,b,f,S,D)其中：f (S,a)=S, f(S,b)=A, f(S,b)=D, f(A,a)=S 其NFA图为：aÞ S bAabDNFA确定化后的状态矩阵为: Qab1SS A,D2A,D SNFA确定化后的DFA为：abÞ 12a给出下述文法所对应的正规式：S->aAA->bA+aB+bB->aA解：将文法改为：S=aA A=bA+aB+b B=aA将代入，得A=bA+aaA+b 将用求解规则，得A= (b|aa)*b ,带入得，S= a(b|aa)*b,故文法所对应的正规式为R= a

10、(b|aa)*b。给出与下图等价的正规文法G。aÞ AaBb Cb abDb答: 该有穷自动机为:M=(A,B,C,D,a,b,f,A,C,D)其中f(A,a)=B, f(A,b)=D, f(B,a)=, f(B,b)=C,f(C,a)=A, f(C,b)=D, f(D,a)=B, f(D,b)=D根据其转换规则，与其等价的正规文法G为G=（A,B,C,D,a,b,P,A）,其中P : AaB|bD BbC CaA|bD| DaB|bD|.解释下列术语和概念：(1)确定有穷自动机答：一个确定有穷自动机M是一个五元组M=（Q，f，S，Z），其中：Q是一个有穷状态集合，每一个元素称为一个

11、状态；是一个有穷输入字母表，每个元素称为一个输入字符；f是一个从Q*到Q的单值映射；f（qi,a）=qj (qi,qjQ,a)表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj,qj称为 qi 的一个后继状态。我们说状态转换函数是单值函数，是指 f（qi,a）惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同。SQ，是惟一的一个初态；Z 真包含于Q，是一个终态集。（2）非确定有穷自动机一个非确定有穷自动机M是一个五元组M=（Q，f，S，Z），其中：Q是一个有穷状态集合，每一个元素称为一个状态；是一个有穷输入字母表，每个元素称为一个输入字符；状态转换函数是

12、一个多值函数。f（qi,a）=某些状态的集合(qiQ)，表示不能由当前状态、当前输入字符惟一地确定下一个要转移的状态，即允许同一个状态对同一输入字符有不同的输出边。S 包含于 A，是非空初态集。Z 真包含于 Q，是一个终态集。（3）正规式和正规集有字母表=a1,a2,an，在字母表上的正规式和它所表示的正规集可用如下规则来定义：（1）是是的正规式，它所表示的正规集是，即空集。（2）是上的正规式，它所表示的正规集仅含一空符号串，即。（3）是上的一个正规式，它所表示的正规集是由单个符号ai 所组成，即ai。（4）e1和e2是是的正规式，它们所表示的正规集分别为L(e1)和L(e2),则e1 |

13、e2是上的一个正规式，它所表示的正规集为 L(e1 | e2)=L(e1)L(e2).e1e2是上的一个正规式，它所表示的正规集为 L(e1e2)=L(e1)L(e2).(e1)*是上的一个正规式，它所表示的正规集为 L(e1)*)=L(e1)*.31构造下列正规式相应的DFA。(1) 1 ( 0 | 1)*101(2) ( a | b )*( aa | bb )( a | b )*(3) ( 0 | 1 )* | ( 11 )*(4) ( 0 | 11*0 )*32将下面图(a)和(b)分别确定化和最小化.aaÞ 0 1 a,b(a)b baÞ 02b3aaaabba145b（b）构造一个DFA，他接收=0，1上所有满足如下条件的字符串，每个1都有0直接跟在右边。给出文法GS，构造相应最小的DFA。 SaS | bA | b AaS给出下述文法所对应的正规式：S->AaA->bA+aB+bB->aA给出与下图等价的正规文法G。aÞ AaBb Cb abDb给出与图中的NFA等价的正规式R。文法G单词为：单词标识符| 整数标识符标识符字母| 标识符数字|字母整数数字|整数数字字母 A | B | C数字1 | 2 | 3（1）改写文法G为G，使L(G)=L(G).（2）给出相应

0/150

联系客服

本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。人人文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知人人文库网，我们立即给予删除！

THE END

编译原理第章习习题课

编译原理第章习习题课

构造下列正规式相应的（b（（abbbab已知＝（｛xyz｝{}{x}{z}），