形式语言与自动机课后习题答案部分.ppt

资源描述

《形式语言与自动机课后习题答案部分.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机课后习题答案部分.ppt（67页珍藏版）》请在三一办公上搜索。

1、2023/10/28,(C)Guohong Fu,CSHLJU,1,课后作业讲解,付国宏黑龙江大学计算机科学技术学院,形式语言与自动机理论,2023/10/28,(C)Guohong Fu,CSHLJU,2,课后作业,作业一：pp.39-41 习题 21,22,23,28(1)(2)(10)作业二：pp.83-85 习题7(1),8(3),9(2)作业三：pp.126-130 习题 1,2(3)(5),7作业四：pp.128-129 习题 11(1),15(1)作业五：pp.129-130 习题 20,21,22 作业六：pp.153-155 习题1(5),2(2),5(2),6(图4-24)

2、作业七：pp.191 习题2(1)(2)作业八：pp.230 习题11(1),12(2)作业九：pp.233 习题 15 作业十：pp.257-258 习题1(1),8(1),2023/10/28,(C)Guohong Fu,CSHLJU,3,课后作业一,pp.39-41：L基本概念习题 21-字母表习题 22-前/后缀习题 23-前/后缀习题 28(1)(2)(10)-L的描述,2023/10/28,(C)Guohong Fu,CSHLJU,4,课后作业一(cont.),pp.40：习题 21判断集合是否字母表的依据非空性有穷性可区分性：字母表中的字符两两互不相同整体性或不可分性解答：(1)

3、、(2)和(6)是字母表，其它不是(3)-不满足非空性(4)a,b,a,c-不满足可区分性(5)0,1,2,n,-不满足有穷性,2023/10/28,(C)Guohong Fu,CSHLJU,5,课后作业一(cont.),pp.40：习题 22解答前缀：,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb,aaaaabbbba真前缀：,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb后缀：,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aa

4、aabbbba,aaaaabbbba真后缀：,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba,2023/10/28,(C)Guohong Fu,CSHLJU,6,课后作业一(cont.),pp.40：习题 23解答前缀：,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba真前缀：,aa,aaaa,aaaaab,aaaaabbb后缀：,ba,bbba,abbbba,aaabbbba,aaaaabbbba真后缀：,ba,bbba,abbbba,aaabbbba注意是任何串的前缀、真前缀、后缀和真后缀；任何串是自身的前缀和

5、后缀，但不是自身的真前缀和真后缀；注意字母表中的字符的整体性。,2023/10/28,(C)Guohong Fu,CSHLJU,7,课后作业一(cont.),pp.40：习题 28(1)(2)(10)(1)L1=0n1n|n1-表示0和1的个数相同，且所有的0位于1之前，长度大于1的0、1串的集合(2)L2=0n1m|n,m1-表示所有的0位于1之前，长度大于1的0、1串的集合(10)L10=0,1,00,01,10,11,000,-表示长度大于0的0、1串的集合,2023/10/28,(C)Guohong Fu,CSHLJU,8,课后作业二,pp.83-85-LG习题7(1)-GL习题8(3

6、)-LG习题9(2)-LG,2023/10/28,(C)Guohong Fu,CSHLJU,9,课后作业二(cont.),pp.84：习题 7(1)用自然语言描述下列文法定义的语言G:AaaA|aaB BBcc|D#cc DbbbD|#解题思路观察每个产生式及其组合产生的子语言的特点；根据开始符的产生式将它们并起来就是整个文法产生的语言；解答(1)D产生式：DbbbD|#使用DbbbD可产生句型：(bbb)mD(m1);进一步使用D#可得：L(D)=(bbb)m#|m0,2023/10/28,(C)Guohong Fu,CSHLJU,10,课后作业二(cont.),(2)B产生式：BBcc|D

7、#cc用产生式BBcc产生句型：B(cc)n(n1);结合BD#cc产生句型：D#cc;利用(1)中的结果，L(B)=(bbb)m#(cc)n|m0，n1(3)A产生式：AaaA|aaB用产生式AaaA产生句型：(aa)kA(k1);结合产生式AaaB产生句型：(aa)kB(k1);利用(1)中的结果，L(A)=(aa)k(bbb)m#(cc)n|k1,m0,n1,2023/10/28,(C)Guohong Fu,CSHLJU,11,课后作业二(cont.),pp.84：习题 8设=0,1，构造产生下列语言的文法(1)所有以0开头的串；(3)所有以11开头，以11结尾的串；8(1)解答分析语言

8、的特点:0 x|x0,1*；产生子语言x|x0,1*的文法A|0A|1A；产生语言0 x|x0,1*的文法S0A；G:S0A A|0A|1A,2023/10/28,(C)Guohong Fu,CSHLJU,12,课后作业二(cont.),习题8(3)的解答分析：语言的特点11x11|x*111,11；产生语言x|x0,1*的文法A|0A|1A；产生子语言11x11|x*的文法S11A11；产生子语言111,11的文法S111|11；G:S11A11|111|11 A|0A|1A,其它答案(1)G:S11A|111|11 A11|0A|1A(2)G:S11A|111|11 AB11 B|0B|1

10、U,14,课后作业三,pp.126-130-DFA习题 1-DFA基本概念习题 2(3)-RL DFA习题 2(5)-RL DFA习题 7-扩展状态转移函数,2023/10/28,(C)Guohong Fu,CSHLJU,15,课后作业三(cont.),pp.126 习题 1(1)图1：q0q3q1q3q2q3q1q3；图2：q0q2q3q1q3q2q3q1(2)DFA识别串的过程的形式描述可用即时描述表示pp.126 习题 2(1),L1=0,1*,2023/10/28,(C)Guohong Fu,CSHLJU,16,课后作业三(cont.),习题 2(3)构造DFA M，使得L(M)=x|

11、x0,1+,且x不含00子串解答：采用画图法根据语言特点定义状态 q0-开始状态；q1-M读到一个0，并等待读一个1；q2-M读到一个1，并等待读更多的1；根据状态定义设计主体框架根据输入字母表补充细节,qt,q2,1,S,q0,q1,0,0,0,1,2023/10/28,(C)Guohong Fu,CSHLJU,17,课后作业三(cont.),习题 2(5)：构造DFA M，使得L(M)=x|x0,1+,且x含形如10110子串解答：画图法(1)根据语言特点定义状态 q0-开始状态，等待读一个1；q1-M读到10110第一个1，并等待读一个0或更多的1；q2-M在读到第一个1后继续读到一个0

12、，并等待读一个1；q3-M在相继读到1和0后读到一个1，并等待读下一个1；q4-M在相继读到1,0和1后读到一个1，并等待读一个0；q5-终止状态：M在相继读到1,0,1和1后读到一个0，并等待读更多的0或1；,2023/10/28,(C)Guohong Fu,CSHLJU,18,课后作业三(cont.),(2)根据状态定义涉及主体框架(3)根据输入字母表补充细节,q1,q5,1,S,q0,q2,0,q3,1,q4,1,0,0,0,1,2023/10/28,(C)Guohong Fu,CSHLJU,19,课后作业三(cont.),pp.127 习题7：设DFA M=(Q,q0,F)，证明：x,

13、y*,(q,xy)=(q,x),y)证明：施归纳于|y|基础：当|y|=0时，y=(q,xy)=(q,x)=(q,x)/x*,x=x(q,x),y)=(q,x),)=(q,x)/pQ,(p,)=p 即(q,xy)=(q,x),y)，结论成立归纳：设当|y|k(k0)时结论成立，往证|y|=k+1结论成立不妨设y=ya,a，显然|ya|=k+1(q,xy)=(q,xya)=(q,xy),a)/扩展状态转移函数定义(q,xa)=(q,x),a)=(q,x),y),a)/归纳假设：(q,xy)=(q,x),y)=(q,x),ya)/扩展状态转移函数定义(q,xa)=(q,x),a)即(q,xya)=

14、(q,x),ya)，结论成立由归纳原理：x,y*,(q,xy)=(q,x),y)成立。,2023/10/28,(C)Guohong Fu,CSHLJU,20,课后作业四,pp.128-129习题 11(1)-NFADFA习题 15(1)-NFANFA,2023/10/28,(C)Guohong Fu,CSHLJU,21,课后作业四(cont.),pp.128 习题 11(1)构造与NFA M等价的DFA M,(1)针对M所有状态的子集S和所有输入符号计算D(S,a),M状态转移表,M状态子集的转移表,解答：子集构造法,2023/10/28,(C)Guohong Fu,CSHLJU,22,课后作

15、业四(cont.),(2)确定可达状态,M状态转移表,M状态转移表,2023/10/28,(C)Guohong Fu,CSHLJU,23,课后作业四(cont.),(3)去除不可达状态,与M等价的DFA M的状态转移表,2023/10/28,(C)Guohong Fu,CSHLJU,24,课后作业四(cont.),pp.129：习题 15(1)：根据下表给定的-NFA M构造与之等价的NFA MN确定FN因为-CLOSURE(q0)=q0,q1,q2F=则FN=F=q3通过计算(q,a)，确定N(q,a)=(q,a)即可得到NFA MN=(Q,N,q0,FN),(q0,0)=-CLOSURE(

16、q0,),0)=-CLOSURE(q0,q1,q2,0)=-CLOSURE(q0,0)(q1,0)(q2,0)=-CLOSURE(q0,q1 q0,q3)=-CLOSURE(q0,q1,q3)=-CLOSURE(q0)-CLOSURE(q1)-CLOSURE(q3)=q0,q1,q2 q1,q2 q0,q1,q2,q3=q0,q1,q2,q3,(q0,1)=-CLOSURE(q0,),1)=-CLOSURE(q0,q1,q2,1)=-CLOSURE(q0,1)(q1,1)(q2,1)=-CLOSURE(q0,q2 q1,q3)=-CLOSURE(q0,q1,q2,q3)=-CLOSURE(q0

17、)-CLOSURE(q1)-CLOSURE(q2)-CLOSURE(q3)=q0,q1,q2 q1,q2 q1,q2 q0,q1,q2,q3=q0,q1,q2,q3,(q1,0)=-CLOSURE(q1,),0)=-CLOSURE(q1,q2,0)=-CLOSURE(q1,0)(q2,0)=-CLOSURE(q0,q3)=-CLOSURE(q0,q3)=-CLOSURE(q0)-CLOSURE(q3)=q0,q1,q2 q0,q1,q2,q3=q0,q1,q2,q3,(q1,1)=-CLOSURE(q1,),1)=-CLOSURE(q1,q2,1)=-CLOSURE(q1,1)(q2,1)=-

18、CLOSURE(q1,q3)=-CLOSURE(q1,q3)=-CLOSURE(q1)-CLOSURE(q3)=q1,q2 q0,q1,q2,q3=q0,q1,q2,q3,(q2,0)=-CLOSURE(q2,),0)=-CLOSURE(q1,q2,0)=-CLOSURE(q1,0)(q2,0)=-CLOSURE(q0,q3)=-CLOSURE(q0,q3)=-CLOSURE(q0)-CLOSURE(q3)=q0,q1,q2 q0,q1,q2,q3=q0,q1,q2,q3,(q2,1)=-CLOSURE(q2,),1)=-CLOSURE(q1,q2,1)=-CLOSURE(q1,1)(q2,1

19、)=-CLOSURE(q1,q3)=-CLOSURE(q1,q3)=-CLOSURE(q1)-CLOSURE(q3)=q1,q2 q0,q1,q2,q3=q0,q1,q2,q3,(q3,0)=-CLOSURE(q3,),0)=-CLOSURE(q0,q1,q2,q3,0)=-CLOSURE(q0,0)(q1,0)(q2,0)(q3,0)=-CLOSURE(q0,q1q0,q3q2,q3)=-CLOSURE(q0,q1,q2,q3)=-CLOSURE(q0)-CLOSURE(q1)-CLOSURE(q2)-CLOSURE(q3)=q0,q1,q2q1,q2 q1,q2 q0,q1,q2,q3=q

20、0,q1,q2,q3,(q3,1)=-CLOSURE(q3,),1)=-CLOSURE(q0,q1,q2,q3,1)=-CLOSURE(q0,1)(q1,1)(q2,1)(q3,1)=-CLOSURE(q0,q2q1,q3 q3)=-CLOSURE(q0,q1,q2,q3)=-CLOSURE(q0)-CLOSURE(q1)-CLOSURE(q2)-CLOSURE(q3)=q0,q1,q2q1,q2 q1,q2 q0,q1,q2,q3=q0,q1,q2,q3,2023/10/28,(C)Guohong Fu,CSHLJU,25,课后作业四(cont.),pp.128：习题 15(2)：根据下表给

21、定的-NFA M4构造与之等价的NFA MN4确定FN4因为-CLOSURE(q0)=q0,q1,q3F3 则FN4=F4 q0=q0,q3通过计算4(q,a)，确定N4=4(q,a)即可得到NFA MN4=(Q,N4,q0,FN4),(q0,0)=-CLOSURE(q0,),0)=-CLOSURE(q0,q1,q3,0)=-CLOSURE(q0,0)(q1,0)(q3,0)=-CLOSURE(q1,q3 q2)=-CLOSURE(q1,q2,q3)=-CLOSURE(q1)-CLOSURE(q2)-CLOSURE(q3)=q1 q2,q3 q3=q1,q2,q3,(q0,1)=-CLOSUR

22、E(q0,),1)=-CLOSURE(q0,q1,q3,1)=-CLOSURE(q0,1)(q1,1)(q3,1)=-CLOSURE(q1 q1,q2 q0)=-CLOSURE(q0,q1,q2)=-CLOSURE(q0)-CLOSURE(q1)-CLOSURE(q2)=q0,q1,q3 q1 q2,q3=q0,q1,q2,q3,(q1,0)=-CLOSURE(q1,),0)=-CLOSURE(q1,0)=-CLOSURE(q1,0)=-CLOSURE(q2)=-CLOSURE(q2)=q2,q3,(q1,1)=-CLOSURE(q1,),1)=-CLOSURE(q1,1)=-CLOSURE(

23、q1,1)=-CLOSURE(q1,q2)=-CLOSURE(q1)-CLOSURE(q2)=q1 q2,q3=q1,q2,q3,(q2,0)=-CLOSURE(q2,),0)=-CLOSURE(q2,q3,0)=-CLOSURE(q2,0)(q3,0)=-CLOSURE(q2,q3)=-CLOSURE(q2,q3)=-CLOSURE(q2)-CLOSURE(q3)=q2,q3 q3=q2,q3,(q2,1)=-CLOSURE(q2,),1)=-CLOSURE(q2,q3,1)=-CLOSURE(q2,1)(q3,1)=-CLOSURE(q0 q0=-CLOSURE(q0)=-CLOSURE(

24、q0)=q0,q1,q3,(q3,0)=-CLOSURE(q3,),0)=-CLOSURE(q3,0)=-CLOSURE(q3,1)=-CLOSURE()=,(q3,1)=-CLOSURE(q3,),1)=-CLOSURE(q3,1)=-CLOSURE(q3,1)=-CLOSURE(q0)=q0,q1,q3,2023/10/28,(C)Guohong Fu,CSHLJU,26,课后作业五,pp.129-130：FARG习题 20-DFA右线性文法习题 21-DFA左线性文法习题 22(1)-右线性文法 FA(2)-左线性文法 FA,2023/10/28,(C)Guohong Fu,CSHLJU

25、,27,课后作业五(cont.),习题20(a)构造DFA M1等价的右线性文法G1,(3)对M1的每个状态转移(q,a)=p，确定相应的产生式qap：(q0,0)=q1 q00q1(q0,1)=q3 q01q3(q1,0)=q0 q10q0(q1,1)=q3 q11q3(q3,0)=q1 q30q1(q3,1)=q1 q31q1,(1)删除不可达状态q2,(3)对M的状态转移(q,a)=pF，确定相应的产生式qa：(q0,1)=q3 q01(q1,1)=q3 q11,G1:q01|0q1|1q3 q11|0q0|1q3 q30q1|1q1,q1,S,q2,0,1,q3,0,1,1,0,0,q

26、0,1,(2)确定V,T和S V=q0,q1,q3 T=0,1 S=q0,2023/10/28,(C)Guohong Fu,CSHLJU,28,课后作业五(cont.),习题20(b)构造DFA M2等价的右线性文法G2,(2)对M2的每个状态转移(q,a)=p，确定相应的产生式qap：(q0,0)=q1 q00q1(q0,1)=q2 q01q2(q1,0)=q2 q10q2(q1,1)=q0 q11q0(q2,0)=q3 q20q3(q2,1)=q1 q21q1(q3,0)=q1 q30q1(q3,1)=q1 q31q1,(3)对M的状态转移(q,a)=pF，确定相应的产生式qa：(q1,1

27、)=q0 q11(q2,0)=q3 q20,G2:q0|0q1|1q2 q11|0q2|1q0 q20|0q3|1q1 q30q1|1q1,(1)确定V,T和S V=q0,q1,q2,q3 T=0,1 S=q0,(4)如果M的开始状态q0又是接受状态,则需引入空产生式q0以产生空语句,2023/10/28,(C)Guohong Fu,CSHLJU,29,课后作业五(cont.),习题21(a)构造DFA M1等价的左线性文法G1,q1,S,q2,0,1,q3,0,1,1,0,0,q0,1,(3)对M1的每个状态转移(A,a)=B，确定相应的产生式BAa：(q0,0)=q1 q1q00(q0,1

28、)=q3 q3q01(q1,0)=q0 q0q10(q1,1)=q3 q3q11(q3,0)=q1 q1q30(q3,1)=q1 q1q31,(1)删除M1不可达状态及相关弧；,(4)对M1的状态转移(A,a)=B，且A为开始状态，确定相应的产生式Ba：(q0,0)=q1 q10(q0,1)=q3 q31,G1:Zq01|q11 q0q10 q10|q00|q30|q31 q31|q01|q11,(5)对M1的状态转移(A,a)=BF，确定相应的产生式ZAa(q0,1)=q3 Zq01(q1,1)=q3 Zq11,(2)确定V,T和S V=q0,q1,q3,Z T=0,1 S=Z,2023/1

29、0/28,(C)Guohong Fu,CSHLJU,30,课后作业五(cont.),习题21(b)构造DFA M2等价的左线性文法G2,(2)对M2的每个状态转移(A,a)=B，确定相应的产生式BAa：(q0,0)=q1 q1q00(q0,1)=q2 q2q01(q1,0)=q2 q2q10(q1,1)=q0 q0q11(q2,0)=q3 q3q20(q2,1)=q1 q1q21(q3,0)=q1 q1q30(q3,1)=q1 q1q31,(3)对M2的状态转移(A,a)=B，且A为开始状态，确定相应的产生式Ba：(q0,0)=q1 q10(q0,1)=q2 q21,G2:Z|q11|q20

30、q0q11 q10|q00|q20|q21 q30|q31 q21|q01|q10 q3q20,(4)对M2的状态转移(A,a)=BF，确定相应的产生式ZAa(q1,1)=q0 Zq11(q2,0)=q3 Zq20,(5)因M2的开始状态又是终止状态，须引入空产生式确定Z来归约空句子,(1)确定V,T和S V=q0,q1,q2,q3,Z T=0,1 S=Z,2023/10/28,(C)Guohong Fu,CSHLJU,31,课后作业五(cont.),pp.129 习题 22(1):构造与所给文法等价的FA,(2)对G中形如AaB的产生式确定相应的状态转移函数(A,a)=B：SaA(S,a)=

31、A AaA(A,a)=A AcA(A,c)=A AbB(A,b)=B BaB(B,a)=B BbB(B,b)=B BcB(B,c)=B,(1)确定Q,q0和F Q=VZ=S,A,B,Z=a,b,c q0=S F=Z,(3)对G中形如Aa的产生式确定相应的状态转移函数(A,a)=Z：Sa(S,a)=Z Aa(A,a)=Z Ba(B,a)=Z Bb(B,b)=Z Bc(B,c)=Z,G1:Sa|aA Aa|aA|cA|bB Ba|b|c|aB|bB|cB,2023/10/28,(C)Guohong Fu,CSHLJU,32,课后作业五(cont.),pp.129 习题 22(2):构造与所给文法等

32、价的FA,(2)对G中形如ABa的产生式确定相应的状态转移函数(B,a)=A：SAa(A,a)=S AAa(A,a)=A AAc(A,c)=A ABb(B,b)=A BBa(B,a)=B BBb(B,b)=B BBc(B,c)=B,(1)确定Q,q0和F Q=VZ=S,A,B,Z=a,b,c q0=Z F=S,(3)对G中形如Aa的产生式确定相应的状态转移函数(Z,a)=A：Sa(Z,a)=S Aa(Z,a)=A Ba(Z,a)=B Bb(Z,b)=B Bc(Z,c)=B,G2:Sa|Aa Aa|Aa|Ac|Bb Ba|b|c|Ba|Bb|Bc,2023/10/28,(C)Guohong Fu

33、,CSHLJU,33,课后作业六,pp.153-155 习题1(5)-RLRE习题2(2)-RERL习题5(2)-REFA习题6(图4-24)-FARE,2023/10/28,(C)Guohong Fu,CSHLJU,34,课后作业六(cont.),习题1(5)写出表示下列语言的正则表达式：(5)x|x0,1+且x含形如10110的子串解答语言x|x0,1+且x含形如10110的子串可等价表示为 0,1*101100,1*0,1*的RE为(0+1)*因此(0+1)*10110(0+1)*即为所求。,2023/10/28,(C)Guohong Fu,CSHLJU,35,课后作业六(cont.),

34、习题2(2)理解如下正则表达式，说明它们表示的语言：(2)(0+1)*0100+解答L(0+1)*0100+)=x|x为以010子串后跟至少一个0组成的串为后缀的任意0和1组成的字符串,2023/10/28,(C)Guohong Fu,CSHLJU,36,课后作业六(cont.),习题5(2)构造下列正则表达式的等价FA：(2)00(0+1)*(01)*+010)00解答,(1)构造与 00等价的-NFA M1;,S,(2)构造与 00(0+1)*等价的-NFA M2;,(3)构造与(01)*等价的-NFA M3;,(4)构造与 010等价的-NFA M4;,(5)构造与(01)*+010等价

35、的-NFA M5;,(6)构造与(01)*+010)00等价的-NFA M6;,(7)构造与 00(0+1)*(01)*+010)00等价的-NFA M7;,2023/10/28,(C)Guohong Fu,CSHLJU,37,课后作业六(cont.),习题6(图4-24)构造下图所示DFA的正则表达式,1,2023/10/28,(C)Guohong Fu,CSHLJU,38,课后作业六(cont.),解答(1)预处理,q1,S,q2,0,q3,0,q0,1,1,0,0,1,q0,q3,X,Y,1,2023/10/28,(C)Guohong Fu,CSHLJU,39,课后作业六(cont.),

36、(2)去状态q3,q1,q2,0,0,1,1,0,0,1,q0,q3,X,Y,1,01,0,00,10,1,11,10,1,11,2023/10/28,(C)Guohong Fu,CSHLJU,40,课后作业六(cont.),(3)合并从标记为q0的状态到标记为q1的状态的两条并行弧,q1,q2,0,1,0,q0,X,Y,01,0,00,10,1,11,10,1,11,+10,2023/10/28,(C)Guohong Fu,CSHLJU,41,课后作业六(cont.),(4)去掉状态q2,q1,q2,1,0,q0,X,Y,01,0,00,10,1,11,1,11,0+10,11(01)*1,

37、11(01)*00,11(01)*0,11(01)*00,11(01)*0,11(01)*1,2023/10/28,(C)Guohong Fu,CSHLJU,42,课后作业六(cont.),(5)合并从标记为q0的状态到标记为q1的状态的两条并行弧,q1,0,q0,X,Y,10,1,1,0+10,11(01)*1,11(01)*00,11(01)*0,11(01)*00,11(01)*0,11(01)*1,+11(01)*00,2023/10/28,(C)Guohong Fu,CSHLJU,43,课后作业六(cont.),(6)合并从标记为q1的状态到标记为q0的状态的两条并行弧,q1,0,q

38、0,X,Y,10,1,1,0+10,11(01)*1,11(01)*0,11(01)*00,11(01)*0,11(01)*1,+11(01)*00,+0,2023/10/28,(C)Guohong Fu,CSHLJU,44,课后作业六(cont.),(7)合并从标记为q0的状态到标记为Y的状态的两条并行弧,q1,q0,X,Y,10,1,1,0+10,11(01)*1,11(01)*0,11(01)*00,11(01)*0,11(01)*1,+11(01)*00,+0,+1+,2023/10/28,(C)Guohong Fu,CSHLJU,45,课后作业六(cont.),(8)合并从标记为q0

39、的状态到标记为Y的状态的两条并行弧,q1,q0,X,Y,10,1,0+10,11(01)*1,11(01)*0,11(01)*00,11(01)*0,11(01)*1,+11(01)*00,+0,+1+,2023/10/28,(C)Guohong Fu,CSHLJU,46,课后作业六(cont.),(9)合并从标记为q1的状态到标记为Y的状态的两条并行弧,q1,q0,X,Y,10,1,0+10,11(01)*1,11(01)*0,11(01)*00,11(01)*0,11(01)*1,+11(01)*00,+0,+1+,+11(01)*0,2023/10/28,(C)Guohong Fu,CS

40、HLJU,47,课后作业六(cont.),(10)合并从标记为q1的状态到标记为q1的状态的两条并行弧,q1,q0,X,Y,10,0+10,11(01)*1,11(01)*0,11(01)*00,11(01)*1,+11(01)*00,+0,+1+,1+11(01)*0,+11(01)*00,2023/10/28,(C)Guohong Fu,CSHLJU,48,课后作业六(cont.),(11)去掉状态q1,q1,q0,X,Y,11(01)*1,11(01)*0,11(01)*1+0,0+10+11(01)*00,+1+,1+11(01)*0,10+11(01)*00,(0+10+11(01)

41、*00)(10+11(01)*00)*(1+11(01)*0),(0+10+11(01)*00)(10+11(01)*00)*(0+11(01)*1),2023/10/28,(C)Guohong Fu,CSHLJU,49,课后作业六(cont.),(12)合并从标记为q0的状态到标记为q0的状态的两条并行弧,q0,X,Y,11(01)*1,11(01)*0,+1+,(0+10+11(01)*00)(10+11(01)*00)*(1+11(01)*0),(0+10+11(01)*00)(10+11(01)*00)*(0+11(01)*1),+11(01)*1,2023/10/28,(C)Guoh

42、ong Fu,CSHLJU,50,课后作业六(cont.),(13)合并从标记为q0的状态到标记为Y的状态的两条并行弧,q0,X,Y,11(01)*0+1+,(0+10+11(01)*00)(10+11(01)*00)*(1+11(01)*0),(0+10+11(01)*00)(10+11(01)*00)*(0+11(01)*1)+11(01)*1,+11(01)*0+1+,2023/10/28,(C)Guohong Fu,CSHLJU,51,课后作业六(cont.),(14)去掉q0,q0,X,Y,(0+10+11(01)*00)(10+11(01)*00)*(1+11(01)*0),(0+

43、10+11(01)*00)(10+11(01)*00)*(0+11(01)*1)+11(01)*1,+11(01)*0+1+,(0+10+11(01)*00)(10+11(01)*00)*(0+11(01)*1)+11(01)*1)*,(0+10+11(01)*00)(10+11(01)*00)*(1+11(01)*0)+11(01)*0+1+),2023/10/28,(C)Guohong Fu,CSHLJU,52,课后作业七,pp.191 习题2-RL泵引理的应用判断下列语言是否是RL。如果不是，证明你的结论；如果是，给出相应的有穷描述。(1)02n|n1(2)0n2|n1,2023/10

44、/28,(C)Guohong Fu,CSHLJU,53,课后作业七(cont.),pp.191 习题2(1)：02n|n1解答：是RL语言：表示偶数个0组成的字串的集合模型：RE:(00)+或00(00)*；RG:S00|00S；-NFA,2023/10/28,(C)Guohong Fu,CSHLJU,54,课后作业七(cont.),pp.191 习题2(2)：0n2|n1解答：不是RL用泵引理证明(1)假设L=0n2|n1 是 RL(2)取z=0N2,zL(3)按照泵引理，一定存在z=uvw，取v=0k(1 k N)，此时u=0N-k-jw=0N2+j-N(4)从而有，uviw=0N-k-j

45、(0k)i0N2+j-N=0N2+(i-1)k,2023/10/28,(C)Guohong Fu,CSHLJU,55,课后作业七(cont.),(5)当i=2时，有：N2+(i-1)k=N2+kN2+N=N(N+1)N2；表明：N2+(i-1)k不是整数的平方；(6)即：i=2时uviwL；这与泵引理矛盾；因此，L不是 RL。,2023/10/28,(C)Guohong Fu,CSHLJU,56,课后作业八,pp.230-CFG的化简习题 11(1)-去无用符习题 12(2)-去空产生式,2023/10/28,(C)Guohong Fu,CSHLJU,57,课后作业八(cont.),pp.23

46、0 习题 11(1)删除下列文法中的无用符号解答方法：先用算法6-1消除不可产生的变量，后用算法6-2消除不可达的符号,(1)用算法6-1删除派生不可产生的变量D和E得到(2)用算法6-2可知，上述文法不存在不可大符号,SAB|CA|aAaBBC|AB|DE|dCaB|b,SAB|CA|aAaBBC|AB|dCaB|b,2023/10/28,(C)Guohong Fu,CSHLJU,58,课后作业八(cont.),pp.230 习题 12(2)消除下列文法中的-产生式解答(1)先用算法6-3找出可空变量集合A,C,D(2)对含有可空变量的产生式分别考虑可能产生和不产生并消除相应的-产生式,(a

47、)去D:只有一种可能(b)去A:两种可能(c)去C:两种可能,SABDCABD|aa|BaB|aCDC|c|D,SABCAB|aa|BaB|aCC|c|,(a),SABC|BCAB|aaBaB|aCC|c|,(b),SABC|BC|AB|BAB|aaBaB|aCc,(c),2023/10/28,(C)Guohong Fu,CSHLJU,59,课后作业九,pp.233 习题15-CFGCNF构造与下列文法等价的CNF SaBB|bAA BaBa|aa|AbbA|,2023/10/28,(C)Guohong Fu,CSHLJU,60,课后作业九(cont.),解答(1)化简删除B删除A,SaBB|

48、aB|a|bAABaBa|aaAbbA|,SaBB|aB|a|bAA|bA|bBaBa|aaAbbA|bb,2023/10/28,(C)Guohong Fu,CSHLJU,61,课后作业九(cont.),(2)引入变量Ca,Cb和产生式Caa，Cbb改造右部长度大于1的产生式，得,(3)引入变量D1,D2和产生式D1CaB,D2CbA 改造右部长度大于2的产生式，得,SCaBB|CaB|CbAA|CbA|a|bBCaBCa|CaCaACbCbA|CbCbCaaCbb,SD1B|CaB|D2A|CbA|a|bBD1Ca|CaCaACbD2|CbCbD1CaBD2CbACaaCbb,2023/10

49、/28,(C)Guohong Fu,CSHLJU,62,课后作业十,pp.257-258习题1(1)-CFL PDA习题8(1)-CFG PDA,2023/10/28,(C)Guohong Fu,CSHLJU,63,课后作业十(cont.),pp.257-258 习题1(1)构造识别下列语言的PDA(1)L=1n0m|nm1解答思路先把输入的字符1入栈；当开始输入0时，从栈中弹出1；若1的个数大于或等于0的个数，则到达终态；此时若1的个数大于0的个数，则栈非空；,2023/10/28,(C)Guohong Fu,CSHLJU,64,课后作业十(cont.),构造设PDA M=(Q,q0,Z0,

50、F)有穷状态集合：Q=q0,q1,q2q0-初态，等待输入1；q1-记录1的状态；q2-匹配状态，比较1和0个数；q3-终止状态，清空栈字符；=0,1；=Z0,1；F=q3；,2023/10/28,(C)Guohong Fu,CSHLJU,65,课后作业十(cont.),根据状态定义和PDA动作设计(q0,1,Z0)=(q1,1Z0)-等待输入1(q1,1,1)=(q1,11)-记录1(q1,0,1)=(q2,)-等到输入“0”(q2,0,1)=(q2,)-匹配(q2,Z0)=(q3,)-0与1个数相等(q2,1)=(q3,)-1的个数比0多(q3,Z0)=(q3,)-空栈(q3,1)=(q3

展开阅读全文