计算理论习题答案 CHAP2 new

2.1 略。

2.2 a. 利用语言A={ambncn | m,n?0}和A={anbncm | m,n?0}以及例3.20，证明上下文无关语言在交的运算下不封闭。

b. 利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。

证明：a.先说明A,B均为上下文无关文法，对A构造CFG C1

S?aS|T|? T?bTc|?

对B,构造CFG C2

S?Sc|R|? R?aRb

由此知 A,B均为上下文无关语言。

但是由例3.20, A∩B={anbncn|n?0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。

b.用反证法。假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，A,B也为CFL，且CFL对并运算封闭，所以A?B也为CFL，进而知道A?B为CFL，由DeMorgan定律A?B＝A∩B，由此A∩B是CFL,这与(a)的结论矛盾，所以CFL对补运算不封闭。

2.3 略。

2.4和2.5 给出产生下述语言的上下文无关文法和PDA，其中字母表?={0,1}。

a. {w | w至少含有3个1} 0, ???

S→A1A1A1A 1, ??1 A→0A|1A|?

?,1?? ?,1?? ?,1??

b. {w | w以相同的符号开始和结束}

S→0A0|1A1 0,??? A→0A|1A|? 1,??? 0,??0 0,0??

1,??1 1,1??

c. {w | w的长度为奇数} 0,???

S→0A|1A 1,??? A→0B|1B|? B→0A|1A

0,???

1,???

d. {w | w的长度为奇数且正中间的符号为0}

S→0S0|1S1|0S1|1S0|0

0,??0 0,0??

1,??0 1,0??

?,??$ 0,??? ?,$??

e. {w | w中1比0多} 1,0?? S→A1A

0,1?? A→0A1|1A0|1A|AA|?

0,??0

1,??1 ?,1??

?,??$ ?,1?? ?,$??

f. {w | w=wR}

S→0S0|1S1|1|0 0,??0 0,0??

1,??1 1,1??

1,???

?,??$ 0,??? ?,$?? ?,??? g. 空集

S→S

2.6 给出产生下述语言的上下文无关文法： a． 字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。 S→bSaSaS|aSbSaS|aSaSbS|?

b．语言{anbn|n?0}的补集。见问题3.25中的CFG: S→aSb|bY|Ta T→aT|bT|?

c．{w#x | w, x?{0,1}*且wR是x的子串}。 S→UV

U→0U0|1U1|W W→W1|W0|# V→0V|1V|?

d．{x1#x2#?#xk|k?1, 每一个xi?{a,b}* , 且存在i和j使得xi＝xjR}。 S→UVW U→A|?

A→aA|bA|#A|# V→aVa|bVb|#B|# B→aB|bB|#B|# W→B|?

2.8 证明上下文无关语言类在并,连接和星号三种正则运算下封闭。

a. A?B

方法一：CFG。设有CFG G1＝(Q1,?,R1,S1)和G2=(Q2,?,R2,S2)且L(G1)=A,

L(G2)=B。构造CFG G=(Q,?,R,S0)，其中

Q= Q1?Q2?{S0}, S0是起始变元，R= R1?R2?{S0? S1|S2}. 方法二：PDA。

设P1=(Q1,?,?1,?1,q1,F1)识别A，P2=(Q1,?,?2,?2,q2,F2)是识别B。 则如下构造的P=(Q,?,?,?,q0,F)识别A?B，其中 1) Q=Q1?Q2?{q0}是状态集， 2) ?＝?1??2，是栈字母表， 3) q0是起始状态，

4) F＝F1?F2是接受状态集，

5) ?是转移函数，满足对任意q?Q, a???,b???

?{(q1,?),(q2,?)},若q?q0,a?b??,??(q,a,b),若q?Q,b?(?),?111??(q,a,b)=?

?(q,a,b),若q?Q,b?(?),222????,else.?b. 连接AB

方法一：CFG。设有CFG G1＝(Q1,?,R1,S1)和G2=(Q2,?,R2,S2)且L(G1)=A, L(G2)=B。构造CFG G=(Q,?,R,S0)，其中

Q= Q1?Q2?{S0}, S0是起始变元，R= R1?R2?{S0? S1S2}. 方法二：PDA。

设P1=(Q1,?,?1,?1,q1,F1)识别A，P2=(Q1,?,?2,?2,q2,F2)是识别B，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。 则如下构造的P=(Q,?,?,?,q1,F)识别A?B，其中 1) Q=Q1?Q2是状态集， 2) ?＝?1??2，是栈字母表， 3) q1是起始状态，

4) F＝F1?F2是接受状态集，

5) ?是转移函数，满足对任意q?Q, a???,b???

?1(q,a,b),若q?Q1?F1,b?(?1)?,???(q,a,b)?{(q,?)},若q?F1,a?b??,12???(q,a,b)=??1(q,a,b),若q?F1,(a,b)?(?,?),

??2(q,a,b),若q?Q2,b?(?2)?,???,else.?

c. A* 方法一：CFG。设有CFG G1＝(Q1,?,R1,S1)，L(G1)=A。构造CFG G=(Q,?,R,S0)，其中Q= Q1 ?{S0}, S0是起始变元，R= R1?{S0?S0S0|S1|?}. 方法二：PDA。

设P1=(Q1,?,?1,?1,q1,F1)识别A，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。

则如下构造的P=(Q,?,?,?,q1,F)识别A*，其中 1) Q=Q1?{q0}是状态集， 2) ?＝?1，是栈字母表，

3) q0是起始状态，

4) F＝F1?{q0}是接受状态集，

5) ?是转移函数，满足对任意q?Q, a???,b???

?1(q,a,b),若q?Q1?F1,???(q,a,b)?{(q,?)},若q?F1,a?b??,11??

?(q,a,b)=??1(q,a,b),若q?F1,(a,b)?(?,?),?(q1,?)若q?q0,a?b??,???,else.?

2.9 证明在3.1节开始部分给出的文法G2中，字符串the girl touches the boy with the flower有两个不同的最左派生，叙述这句话的两个不同意思。 <句子>

?<名词短语><动词短语> ?<复合名词><动词短语> ?<冠词><名词><动词短语> ?a_<名词><动词短语> ?a_girl_<动词短语> ?a_girl_<复合名词>

?a_girl_<动词>< 名词短语> ?a_girl_touches_< 名词短语>

? a_girl_touches_<复合名词><介词短语> ?a_girl_touches_<冠词><名词><介词短语> ?a_girl_touches_the_<介词><复合名词> ?a_girl_touches_the_boy_<介词短语>

?a_girl_touches_the_boy_<介词><复合名词> ?a_girl_touches_the_boy_with_<复合名词> ?a_girl_touches_the_boy_with_<冠词><名词> ?a_girl_touches_the_boy_with_the_<名词> ?a_girl_touches_the_boy_with_the_flower 含义是 ：女孩碰这个带着花的男孩

<句子>

?<名词短语><动词短语> ?<复合名词><动词短语> ?<冠词><名词><动词短语> ?a_<名词><动词短语> ?a_girl_<动词短语>

?a_girl_<复合动词><介词短语>

?a_girl_<动词>< 名词短语><介词短语> ?a_girl_touches_< 名词短语><介词短语> ?a_girl_touches_<冠词><名词><介词短语> ?a_girl_touches_the_< 名词><介词短语>