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

1、2020/8/17,(C)Guohong Fu, CSHLJU,1,课后作业讲解,付国宏 黑龙江大学计算机科学技术学院,形式语言与自动机理论,2020/8/17,(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、(2), 5(2), 6(图4-24) 作业七：pp.191 习题2 (1) (2) 作业八：pp.230 习题11(1), 12(2) 作业九：pp.233 习题 15 作业十：pp.257-258 习题1(1), 8(1),2020/8/17,(C)Guohong Fu, CSHLJU,3,课后作业一,pp.39-41：L基本概念 习题 21 -字母表 习题 22 - 前/后缀 习题 23 - 前/后缀 习题 28(1)(2)(10) - L的描述,2020/8/17,(C)Guohong Fu, CSHLJU,4,课后作业一 (cont.),pp.40：习题 21 判断集合是否字母表的依

3、据 非空性 有穷性 可区分性：字母表中的字符两两互不相同 整体性或不可分性 解答：(1)、(2) 和(6) 是字母表，其它不是 (3) - 不满足非空性 (4) a, b, a, c - 不满足可区分性 (5) 0, 1, 2, , n, -不满足有穷性,2020/8/17,(C)Guohong Fu, CSHLJU,5,课后作业一(cont.),pp.40：习题 22 解答 前缀：, a, aa, aaa, aaaa, aaaaa, aaaaab, aaaaabb, aaaaabbb, aaaaabbbb, aaaaabbbba 真前缀：, a, aa, aaa, aaaa, aaaaa,

4、aaaaab, aaaaabb, aaaaabbb, aaaaabbbb 后缀：, a, ba, bba, bbba, bbbba, abbbba, aabbbba, aaabbbba, aaaabbbba, aaaaabbbba 真后缀：, a, ba, bba, bbba, bbbba, abbbba, aabbbba, aaabbbba, aaaabbbba,2020/8/17,(C)Guohong Fu, CSHLJU,6,课后作业一(cont.),pp.40：习题 23 解答 前缀：, aa, aaaa, aaaaab, aaaaabbb, aaaaabbbba 真前缀：, aa,

5、aaaa, aaaaab, aaaaabbb 后缀：, ba, bbba, abbbba, aaabbbba, aaaaabbbba 真后缀：, ba, bbba, abbbba, aaabbbba 注意 是任何串的前缀、真前缀、后缀和真后缀； 任何串是自身的前缀和后缀，但不是自身的真前缀和真后缀； 注意字母表中的字符的整体性。,2020/8/17,(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|

6、n, m1 -表示所有的0位于1之前，长度大于1的0、1串的集合 (10) L10=0, 1, 00, 01, 10, 11, 000, -表示长度大于0的0、1串的集合,2020/8/17,(C)Guohong Fu, CSHLJU,8,课后作业二,pp.83-85 - LG 习题7(1) - GL 习题8(3) - LG 习题9(2) - LG,2020/8/17,(C)Guohong Fu, CSHLJU,9,课后作业二 (cont.),pp.84：习题 7(1) 用自然语言描述下列文法定义的语言 G: AaaA|aaB BBcc|D#cc DbbbD|# 解题思路 观察每个产生式及其组

7、合产生的子语言的特点； 根据开始符的产生式将它们并起来就是整个文法产生的语言； 解答 (1) D产生式：DbbbD|# 使用DbbbD可产生句型：(bbb)mD (m1); 进一步使用D#可得：L(D)=(bbb)m#| m0,2020/8/17,(C)Guohong Fu, CSHLJU,10,课后作业二 (cont.),(2) B产生式：BBcc|D#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

8、(k1); 结合产生式AaaB产生句型：(aa)kB(k1); 利用(1)中的结果， L(A)=(aa)k(bbb)m# (cc)n|k1, m0, n1,2020/8/17,(C)Guohong Fu, CSHLJU,11,课后作业二 (cont.),pp.84：习题 8 设=0, 1，构造产生下列语言的文法 (1) 所有以0开头的串； (3) 所有以11开头，以11结尾的串； 8(1)解答 分析语言的特点: 0 x|x0, 1*； 产生子语言x|x0, 1*的文法 A|0A|1A； 产生语言0 x|x0, 1*的文法 S0A； G: S0A A|0A|1A,2020/8/17,(C)Guo

9、hong 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|1B,2020/8/17,(C)Guohong Fu, CSHLJU,13,课后作业二 (cont.),pp.84：习题 9(2) 设

10、=a, b, c，构造产生下列语言的文法 (2) L2=anbm|m,n1； 解答 分析语言的特点：表示至少一个a和至少一个b构成，且所有的a位于b之前的a、b串的集合。 产生子语言La=an|n1的文法：Ga: Aa|aA 产生子语言Lb=bm|m1的文法：Gb: Bb|bB 利用L2=anbm|m,n1同子语言La、Lb的关系，即L2=LaLb，可得文法 G2: S AB - a子串和b子串的位置关系 A a | aA B b | bB;,2020/8/17,(C)Guohong Fu, CSHLJU,14,课后作业三,pp.126-130 - DFA 习题 1 - DFA基本概念 习题

11、2(3) - RL DFA 习题 2(5) - RL DFA 习题 7 - 扩展状态转移函数,2020/8/17,(C)Guohong Fu, CSHLJU,15,课后作业三 (cont.),pp.126 习题 1 (1) 图1：q0q3q1q3q2q3q1q3；图2：q0q2q3q1q3q2q3q1 (2) DFA识别串的过程的形式描述可用即时描述表示 pp.126 习题 2(1),L1=0, 1*,2020/8/17,(C)Guohong Fu, CSHLJU,16,课后作业三 (cont.),习题 2(3)构造DFA M，使得L(M)=x|x0,1+,且x不含00子串 解答：采用画图法

12、根据语言特点定义状态 q0-开始状态； q1- M读到一个0，并等待读一个1； q2- M读到一个1，并等待读更多的1； 根据状态定义设计主体框架 根据输入字母表补充细节,qt,q2,1,S,q0,1,q1,0,0,1,0,0,1,2020/8/17,(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，

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

14、设DFA M=(Q, , , q0, F)，证明：x, 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,

15、x), y), a) /归纳假设： (q, xy)= (q, x), y) = (q, x), ya) /扩展状态转移函数定义(q, xa)=(q, x), a) 即(q, xya)=(q, x), ya)，结论成立 由归纳原理： x, y*, (q, xy)= (q, x), y)成立。,2020/8/17,(C)Guohong Fu, CSHLJU,20,课后作业四,pp.128-129 习题 11(1) - NFADFA 习题 15(1) - -NFANFA,2020/8/17,(C)Guohong Fu, CSHLJU,21,课后作业四 (cont.),pp.128 习题 11(1)

16、构造与NFA M等价的DFA M,(1) 针对M所有状态的子集S和所有输入符号计算D(S, a),M状态转移表,M状态子集的转移表,解答：子集构造法,2020/8/17,(C)Guohong Fu, CSHLJU,22,课后作业四 (cont.),(2) 确定可达状态,M状态转移表,M状态转移表,2020/8/17,(C)Guohong Fu, CSHLJU,23,课后作业四 (cont.),(3) 去除不可达状态,与M等价的DFA M的状态转移表,2020/8/17,(C)Guohong Fu, CSHLJU,24,课后作业四(cont.),pp.129：习题 15(1)：根据下表给定的-N

17、FA 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(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, q

18、1, 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) -CLOSURE(q1) -CLOSURE(q2) -CLOSURE(q3) = q0, q1, q2 q1, q2 q1, q2 q0, q1, q2, q3 = q0, q1, q2, q3,(q1

19、, 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) = -CLOSURE( q1 , q3) = -CLOSURE(q1, q3)

20、= -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

21、, 1) = -CLOSURE(q1, 1) (q2, 1) = -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) = -C

22、LOSURE(q0) -CLOSURE(q1) -CLOSURE(q2) -CLOSURE(q3) = q0, q1, q2q1, q2 q1, q2 q0, q1, q2, q3 = q0, 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

23、) -CLOSURE(q3) = q0, q1, q2q1, q2 q1, q2 q0, q1, q2, q3 = q0, q1, q2, q3,2020/8/17,(C)Guohong Fu, CSHLJU,25,课后作业四(cont.),pp.128：习题 15(2)：根据下表给定的-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, ),

24、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)=-CLOSURE(q0, ), 1) = -CLOSURE(q0,q1,q3, 1) = -CLOSURE(q0, 1) (q1, 1) (q3, 1) = -CLOSURE(q1 q1, q2 q0) = -CLOSURE(q0,q1,q

25、2) = -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(q1, 1) = -CLOSURE(q1, q2) = -CLOSURE(q1) -CLOSURE(q2) = q1

26、 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) = -CLOSUR

27、E(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,2020/8/17,(C)Guohong Fu, CSHLJU,26,课后作业五,pp.129-130 ：FARG 习题 20 - DFA右线性文法 习题 21 - DFA左线性文法 习题 22 (1) -右线性文法 FA

28、 (2) -左线性文法 FA,2020/8/17,(C)Guohong Fu, CSHLJU,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)=

29、q3 q11,G1: q01|0q1|1q3 q11|0q0|1q3 q30q1|1q1,q1,S,q2,0,1,q3,0,1,1,0,0,q0,1,(2)确定V, T和S V=q0, q1, q3 T=0, 1 S=q0,2020/8/17,(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)=

30、q3 q20q3 (q2, 1)=q1 q21q1 (q3, 0)=q1 q30q1 (q3, 1)=q1 q31q1,(3)对M的状态转移 (q, a)=pF，确 定相应的产生式 qa： (q1, 1)=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以产生空语句,2020/8/17,(C)Guohong Fu, CSHLJU,29,课后作业五(cont.),

31、习题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)=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

32、 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,2020/8/17,(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 q2

33、q10 (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 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的开始

34、状态又 是终止状态，须引入 空产生式确定Z来 归约空句子,(1)确定V, T和S V=q0, q1, q2, q3, Z T=0, 1 S=Z,2020/8/17,(C)Guohong Fu, CSHLJU,31,课后作业五(cont.),pp.129 习题 22(1): 构造与所给文法等价的FA,(2)对G中形如AaB的产 生式确定相应的状态转移 函数(A, a)=B： SaA (S, a)=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 =

35、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,2020/8/17,(C)Guohong Fu, CSHLJU,32,课后作业五(cont.),pp.129 习题 22(2): 构造与所给文法等价的FA,(2)对G中形如ABa的产 生式确定相应的状态转移 函数(B, a)=A： SAa (A, a)=S AAa (A

36、, 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,2020/8/17,(C)Guohong Fu, CSHLJU,33,课后作业六,p

37、p.153-155 习题1(5) - RLRE 习题2(2) - RERL 习题5(2) - REFA 习题6(图4-24) - FARE,2020/8/17,(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)*即为所求。,2020/8/17,(C)Guohong Fu, CSHLJU,35,课后作业六 (

38、cont.),习题2(2) 理解如下正则表达式，说明它们表示的语言： (2) (0+1)*0100+ 解答 L(0+1)*0100+)=x|x为以010子串后跟至少一个0组成的串为后缀的任意0和1组成的字符串,2020/8/17,(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

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

40、hong Fu, CSHLJU,39,课后作业六 (cont.),(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,2020/8/17,(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,2020/8/17,(C)Guohong Fu, CSHLJU,41,课后作业六 (cont.),(4) 去掉状态q2,q1,q2,1,0,q0,X

41、,Y,01,0,00,10,1,11,1,11,0+10,11(01)*1,11(01)*00,11(01)*0,11(01)*00,11(01)*0,11(01)*1,2020/8/17,(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,2020/8/17,(C)Guohong Fu, CSHLJU,43,课后作业六 (co

42、nt.),(6) 合并从标记为q1的状态到标记为q0的状态的两条并行弧,q1,0,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,2020/8/17,(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+,2020/8/17,(C)Gu

43、ohong Fu, CSHLJU,45,课后作业六 (cont.),(8) 合并从标记为q0的状态到标记为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+,2020/8/17,(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)

44、*00,+0,+1+,+11(01)*0,2020/8/17,(C)Guohong Fu, CSHLJU,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,2020/8/17,(C)Guohong Fu, CSHLJU,48,课后作业六 (cont.),(11) 去掉状态q1,q1,q0,X,Y,11(01)*1,11(01)*0,11(01)*1+0,0+1

45、0+11(01)*00,+1+,1+11(01)*0,10+11(01)*00,(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),2020/8/17,(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

46、)(10+11(01)*00)*(0+11(01)*1),+11(01)*1,2020/8/17,(C)Guohong 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+,2020/8/17,(C)Guohong Fu, CSHLJU,51,课后作业六 (cont.),(

47、14) 去掉q0,q0,X,Y,(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+,(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+),2020/8/17,(C)Guohong Fu, CSHLJU,52,课后作业七,pp.191 习题2 - RL泵引

48、理的应用 判断下列语言是否是RL。如果不是，证明你的结论；如果是，给出相应的有穷描述。 (1) 02n|n1 (2) 0n2|n1,2020/8/17,(C)Guohong Fu, CSHLJU,53,课后作业七 (cont.),pp.191 习题2(1)： 02n|n1 解答：是RL 语言：表示偶数个0组成的字串的集合 模型： RE: (00)+或00(00)*； RG: S00|00S； -NFA,2020/8/17,(C)Guohong Fu, CSHLJU,54,课后作业七 (cont.),pp.191 习题2 (2)：0n2|n1 解答：不是RL 用泵引理证明 (1)假设L=0n2|

49、n1 是 RL (2) 取z=0N2, zL (3) 按照泵引理，一定存在z=uvw， 取v=0k(1 k N)，此时 u=0N-k-j w=0N2+j-N (4) 从而有， uviw=0N-k-j(0k)i0N2+j-N=0N2+(i-1)k,2020/8/17,(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。,2020/8/17,(C)Guohong Fu, CSH

50、LJU,56,课后作业八,pp.230 - CFG的化简 习题 11(1) - 去无用符 习题 12(2) - 去空产生式,2020/8/17,(C)Guohong Fu, CSHLJU,57,课后作业八 (cont.),pp.230 习题 11(1) 删除下列文法中的无用符号 解答 方法：先用算法6-1消除不可产生的变量，后用算法6-2消除不可达的符号,(1) 用算法6-1删除派生不可产生的变量D和E得到 (2) 用算法6-2可知，上述文法不存在不可大符号,SAB|CA|a Aa BBC|AB|DE|d CaB|b,SAB|CA|a Aa BBC|AB|d CaB|b,2020/8/17,(C)Guohong Fu, CSHLJU,58,课后作业八 (cont.),pp.230 习题 12(2) 消除下列文法中的-产生式 解答 (1) 先用算法6-3找出可空变量集合A, C, D (2) 对含有可空变量的产生式分别考虑可能产生和不产生并消除相应的-产生式,(a)去D:只有一种可能 (b)去A: 两种可能 (c)去C: 两种可能,SABDC ABD|aa| BaB|a CDC|c| D,SABC AB|aa| BaB|a CC|c|,(a),SABC|BC AB|aa BaB|a CC|c|,(b),