计算理论课后习题答案

1、第一章 习题,1给定文法G=(S,B,C,D,E,0,1,P,S)，其中P： SABC，AB0AD，AB1AE，AB，D00D，D11D，E00E， E11E， C， DCB0C，ECB1C，0BB0，1BB1 试写出句子01100110的派生过程。 解：SABC0ADC0AB0C01AE0C01A0EC 01A0B1C01AB01C011AE01C011A0E1C 011A01EC011A01B1C011A0B11C011AB011C 0110AD011C0110A0D11C0110A01D1C 0110A011DC0110A011B0C0110A01B10C 0110A0B110C0110AB0110C01100110C01100110,2设计下列各文法G，使得它们分别是： （1）G是个上下文无关文法，且 L(G)=aibj ck i,j,k1。 （2）G是个正规文法，且 L(G)=aibj ck i,j,k1。 （3）G是个上下文无关文法，且 L(G)= wwRw0,1+ 。其中wR是w的逆转，例 如w=001, 则wR=100. 解：设计一个文法G要验证： 凡是符合要求的句子G

2、都能产生出来； G产生出来的所有句子都是符合要求的。 (1) G=(S,A,B,C,a,b,c,P,S) P: SABC , AaA|a, BbB|b,CcC|c,(2) G=(S,A,B,C,a,b,c,P,S) P: SaA , AaA| bB, BbB|cC, CcC| (3) G=(S,0,1,P,S) P: S0S0|1S1|00|11,第二章 习题,1设计一个有限自动机(FA) M，使得T(M)中的每个句 子w同时满足下面三个条件： 1) wa,b,*； 2) |w|是3的整数倍； 3) w以a开头，以b结尾。 解：,2设计二个FA M1和M2，分别满足 T(M1)=02ii是自然数 T(M2)=02i+1i=0,1,2,3,4, 解： M1 ：,3. 给定NFA M1 =(p,q,r,s,0,1,p,s)，如下表所示。 构造一个DFA M2，使得T(M1)=T(M2) 。 解：令 M2=(K, , q0,F), 其中 K2K，K中的元素是由K的子集 q1,q2,qi构成，但是要把子集 q1,q2,qi作为的一个状态看待， 因此把此子集写成q1,q2,qi。 q0=q0 ,

3、 F=q1,q2,qi|q1,q2,qiK且q1,q2,qiF ：KK，对q1,q2,qiK, a，有 (q1,q2,qi,a)=p1,p2,pj 当且仅当 (q1,q2,qi,a)=p1,p2,pj,q0=p , K和F以后确定。 ：,p,0,1,p,q,p,p,q,p,q,r,p,r,p,r,p,q,s,p,p,q,r,p,q,r,s,p,r,p,q,s,p,q,r,s,p,r,s,p,r,s,p,q,s,p,s,p,s,p,q,s,p,s,p,q,r,s,p,q,r,s,p,r,s,K=p,p,q,p,r,p,s,p,q,r,p,q,s,p,r,s,p,q,r,s F = p,s,p,q,s,p,r,s,p,q,r,s,0,1,0,0,0,0,0,0,1,0,1,1,1,1,1,1,4.将下面的-NFA M等价变换成NFA M。, ：对任何qK,任何a, (q,a)= (q,a) 。,解：M=(K, , ,q0 ,F)，q0是M的开始状态，其中,公式(1)：对于qK, , (q,)=-CLOSURE(q),公式(2)： 对于qK, w*, a,(q,wa)=-CLOSURE( (

4、q,w),a),因为fCLOSURE(a)=a,b, 所以F=F=f ：qK,任何a,(q,a)= (q,a) 。,在计算 (q,a)时，要将a理解成a路径！,例如(a,0)= (a,0)=c,e,d,b 。,:,0,1,abcdef,c,e,d,b,d,b,d,b,f,f,d,b,f,d,b,f,f,d,b,5化简正规表达式 a(+aa)*(+a)b+b+(ab*+b)*。 解：上式a(aa)*(+a)b+b 其中(aa)*(+a)代表集合： ,aa,aaaa,aaaaaa,a = ,aa,aaaa,aaaaaa,a,aaa,aaaaa, =,a,aa,aaa,aaaa,aaaaa,aaaaaa,=a* 于是上式aa*b+b=a+ b+b= (a+)b= a*b,6构造一个FA M，使得T(M)的正规表达式为 01+(0+1)*1)*。 解：1.分解表达式，找出基本单元：0,1,01,1。设计接收 这些基本单元的自动机如下：,2.组装： （按照优先权从高到低） 01+(0+1)*1)*,1,0,1,0,1,7给定FA M如下图所示，求它所接收的语言T(M)的正 规表达式。 解：,8.

5、将下面有限自动机简化(要求有简化过程)。 解：一.定义K上等价关系 给定DFA M=(K,q0,F)， p,qK, pq 对 x*, 有 (p,x)F(q,x)F 如果pq 也称p与q是不可区分的。 二.商集K/ 三的逆关系 pq x(x*(p,x)F(q,x)F) x(x* (p,x)F(q,x)F)(p,x)F(q,x)F) x(x*，使得(p,x)与(q,x)恰有一个在F中 ) 如果pq, 称p与q是可区分的。判断pq是比较容易的。,4判断可区分状态对的算法 引理2-1 设M=(K,q0,F)是DFA，则状态对(p,q)是可区分 的(即pq)，当且仅当在下面算法中(p,q)格写上。 begin 1for pF,qK-F, do 给(p,q)格写； 2for FF或(K-F)(K-F)中每个状态对(p,q) (pq)，do 3if a，使得格(p,a),(q,a)内已经写上，then begin 4 给(p,q)格写； 5 如果刚刚写上的格内有先前写入的状态对，此状态对 的格同时也写入。反复执行5, 直到写入的格内没 有先前写入的状态对为止； end else /* 格(p,a),

6、(q,a)内无 */ 6for 每个a, do 7把(p,q)写入格(p,a),(q,a)内，除非(p,a)=(q,a)。 end,执行此算法的结果用一个表表示，实际上，执行此算 法的过程就是向这个表内写入“”的过程。, ,(b,d), ,(a,b):,be,?,(a,c):,ba,(a,d):,bf,(b,c):,(b,d):,(c,d):,(e,f):,ea,ef,fe,af,dd,fe,得：bd, ef , aa ,cc,于是 K/a,b,d,c,e,f， 五构造简化的有限自动机 定理2-5.1 给定DFA M(K,q0,F)，可根据引理2-1中 的算法构造出除去不可达状态的具有更少状态的DFA M， 使得T(M)=T(M)。 证明：先对M用引理2-1中的算法求出K/。再构造M： M=(K,q0, F)，其中 K=q| qK/且在M中q是从q0 可达的状态 F=q| qF ：对任何qK，任何a, (q,a)=(q,a),K/a,b,d,c,e,f=a,b,c,e，(b=b,d,e=e,f) K= a,b,c,e F=e M=(K,a, F) =(a,b,c,e,0,1,a,e)

7、(q,a)=(q,a),:,0 1,abce,b,c,b,e,a,a,e,e,9给定DFA M如图所示。求一个左线性文法G，使得 L(G)=T(M)。 解：有两种方法。 方法1 1.先将M逆转成M：,2.根据M构造右线性文法G：,SA|C| A0B B0A|0C|1C|0 C1A|1B|1,3.将G逆转成左线性文法G:,SA|C| AB0 BA0|C0|C1|0 CA1|B1|1,P=qap|(q,a)=pqa|(q,a)F。,方法2 1.先根据M构造右线性文法G： A0B|1C|1 (其中A是开始变元) B0A|1C|0|1 C0B|1B 2.再将G直接变成左线性文法G: 根据定理： (1) S, 当且仅当 SP； (2) Ai, 当且仅当 SAiP； (3) AiAj, 当且仅当 AjAiP； (4) SAj, 当且仅当 AjP。 (1)由A1 得: A1 (2) 由A0B 得: B0 由A1C 得: C1 (3)由B0A 得:A B0 由B1C 得: CB1 由C0B 得:BC0 由C1B 得: BC1 (4)由 B0 得: AB0 由B1 得: AB1,方法2 1.先根据M构造右线性文法G： A0B|1C|1 |(其中A是开始变元) B0A|1C|0|1 C0B|1B 因开始变元A出现在产生式右侧，故引入新的开始变元S， SA (其中S是开始变元) A0B|1C|1| B0A|1C|0|1 C0B|1B,2.再将G直接变成左线性文法G: 根据定理： (1) S, 当且仅当 SP； (2) Ai, 当且仅当 SAiP； (3) AiAj, 当且仅当 AjAiP； (4) SAj, 当且仅当 AjP。 (2) SA 得: A (3) 由A0B 得: BA0 由A1C 得: CA1 由B0A 得:A B0 由B1C 得: CB1 由C0B 得:BC0 由C1B 得: BC1 (4)由A1 得: SA1 由A 得: SA 由 B0 得: SB0 由B1 得: SB1,整理得左线性文法G: SA1|B0 |B1|A A B0| BA0| C0 | C1 CA1|B1 表面上看与方法1得结果略有些不同 SA|C| AB0 BA0|C0|C1|0 CA1|B1|1,10首先构造一个右线性文法G，使得 L(G)=ai bj|

《计算理论课后习题答案》由会员suns****4568分享，可在线阅读，更多相关《计算理论课后习题答案》请在金锄头文库上搜索。