计算理论习题答案CHAP2new.docx
《计算理论习题答案CHAP2new.docx》由会员分享，可在线阅读，更多相关《计算理论习题答案CHAP2new.docx（14页珍藏版）》请在冰点文库上搜索。
计算理论习题答案CHAP2new
2.2a.利用语言A={ambncn|m,n0}和A={anbncm|m,n0}以及例3.20，证明上下文无关语言在交的运算下不封闭。
b.利用（a）和DeMorgan律（定理1.10），证明上下文无关语言在补运算下不封闭。
证明：
a.先说明A,B均为上下文无关文法，对A构造CFGC1
SaS|T|
TbTc|
对B,构造CFGC2
SSc|R|
RaRb
由此知A,B均为上下文无关语言。
但是由例3.20,A∩B={anbncn|n0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。
b.用反证法。
假设CFL在补运算下封闭，则对于（a）中上下文无关语言A,B，
也为CFL，且CFL对并运算封闭，所以
也为CFL，进而知道
为CFL，由DeMorgan定律
＝A∩B，由此A∩B是CFL,这与（a）的结论矛盾，所以CFL对补运算不封闭。
2.4和2.5给出产生下述语言的上下文无关文法和PDA，其中字母表={0,1}。
a.{w|w至少含有3个1}
S→A1A1A1A
A→0A|1A|
b.{w|w以相同的符号开始和结束}
S→0A0|1A1
A→0A|1A|
c.{w|w的长度为奇数}
S→0A|1A
A→0B|1B|
B→0A|1A
d.{w|w的长度为奇数且正中间的符号为0}
S→0S0|1S1|0S1|1S0|0
e.{w|w中1比0多}
S→A1A
A→0A1|1A0|1A|AA|
f.{w|w=wR}
S→0S0|1S1|1|0
g.空集
S→S
2.6给出产生下述语言的上下文无关文法：
a．字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。
S→bSaSaS|aSbSaS|aSaSbS|
b．语言{anbn|n0}的补集。
见问题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|k1,每一个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.AB
方法一：
CFG。
设有CFGG1＝（Q1,,R1,S1）和G2=（Q2,,R2,S2）且L（G1）=A,L（G2）=B。
构造CFGG=（Q,,R,S0），其中
Q=Q1Q2{S0},S0是起始变元，R=R1R2{S0S1|S2}.
方法二：
PDA。
设P1=（Q1,,1,1,q1,F1）识别A，P2=（Q1,,2,2,q2,F2）是识别B。
则如下构造的P=（Q,,,,q0,F）识别AB，其中
1）Q=Q1Q2{q0}是状态集，
2）＝12，是栈字母表，
3）q0是起始状态，
4）F＝F1F2是接受状态集，
5）是转移函数，满足对任意qQ,a,b
（q,a,b）=
b.连接AB
方法一：
CFG。
设有CFGG1＝（Q1,,R1,S1）和G2=（Q2,,R2,S2）且L（G1）=A,L（G2）=B。
构造CFGG=（Q,,R,S0），其中
Q=Q1Q2{S0},S0是起始变元，R=R1R2{S0S1S2}.
方法二：
PDA。
设P1=（Q1,,1,1,q1,F1）识别A，P2=（Q1,,2,2,q2,F2）是识别B，而且P1满足在接受之前排空栈（即若进入接受状态，则栈中为空）这个要求。
则如下构造的P=（Q,,,,q1,F）识别AB，其中
1）Q=Q1Q2是状态集，
2）＝12，是栈字母表，
3）q1是起始状态，
4）F＝F1F2是接受状态集，
5）是转移函数，满足对任意qQ,a,b
（q,a,b）=
c.A*
方法一：
CFG。
设有CFGG1＝（Q1,,R1,S1），L（G1）=A。
构造CFGG=（Q,,R,S0），其中Q=Q1{S0},S0是起始变元，R=R1{S0S0S0|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）是转移函数，满足对任意qQ,a,b
（q,a,b）=
2.9证明在3.1节开始部分给出的文法G2中，字符串thegirltouchestheboywiththeflower有两个不同的最左派生，叙述这句话的两个不同意思。
<句子>
<名词短语><动词短语>
<复合名词><动词短语>
<冠词><名词><动词短语>
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_< 名词><介词短语>
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
含义是：
女孩用花碰这个男孩
2.10给出产生语言A={aibjck|i,j,k0且或者i=j或者j=k}的上下文无关文法。
你给出的文法是歧义的吗？
为什么？
解：
下面是产生A的一个CFG:
SUV|AB
UaUb|
VcV|
AaA|
BbUc|
这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生：
SUVaUbVabVabcVabc
SABaAVaVabVcabc
2.11给出识别2.10中语言A的下推自动机的非形式描述。
解：
其非形式描述为：
此PDA有两个非确定性的分支：
一个分支先读a，并且每读一个a将一个a推入栈中，当碰到b时，每读一个b从栈中弹出一个a，若没有a可弹出则拒绝，最后读c且不改变栈中的内容，若此时栈为空则接受。
另一个分支也是先读a，但不改变栈中内容，当碰到b时，每读一个b将一个b推入栈中，再读c,每读一个c从栈中弹出一个b，若没有a可弹出则拒绝，若c读完后栈为空则接受。
开始时，读输入串的字符，非确定性的选择一个分支运行，若有一个分支接受则接受，否则拒绝。
2.14设有上下文无关文法G:
STT|U
U0U00|#
T0T|T0|#
a.用普通的语言描述L（G）。
b.证明L（G）不是正则的。
解：
a.A={0i#0j#0k|i,j,k0}{0i#02i|i0}。
b.取s=0p#02p,则对于任意划分s=xyz（|xy|p,|y|>0）,xynz=0p+i#02pA,所以不是正则的。
2.15用定理2.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。
ABAB|B|
B00|
解：
添加新起始变元S0,去掉B
S0AS0A
ABAB|B|ABAB|AB|BA|B|
B00|B00
去掉A,去掉AB
S0AS0A
ABAB|AB|BA|B|BBABAB|AB|BA|00|BB
B00B00
去掉S0A,添加新变元
S0BAB|AB|BA|00|BBS0VB|AB|BA|UU|BB
ABAB|AB|BA|00|BBAVB|AB|BA|UU|BB
B00BUU
VBA
U0
2.x先说明如何把正则表达式直接转换成等价得上下文无关文法，然后利用问题xxx的结果，给出每一个正则语言都是上下文无关文法的一个证明。
解：
设有正则表达式T，将其转化为上下文无关文法。
1）首先添加ST，且令S为起始变元。
2）根据T的不同形式，按如下方式添加规则
1．若T＝a，则在规则集中添加Ta,
2．若T＝，则在规则集中添加T,
3．若T＝，则在规则集中添加TT，
4．若T＝AB，则在规则集中添加TA|B，
5．若T＝A·B,则在规则集中添加TAB，
6．若T＝A*,则在规则集中添加TA,和AAA|
3）若有新添加的变元，则根据其所对应的表达式转第2步，直到没有新的变元出现。
下面来证明每一个正则语言都是上下文无关的
由正则语言与正则表达式的等价性可知：
对于一个正则语言都存在一个描述他的正则表达式，由前述讨论可知，这个正则表达式可转换为一个与之等价的上下文无关的文法。
因此，此正则语言能由这个上下文无关文法产生。
所以正则语言是上下文无关的。
2.18a.设C是上下文无关语言，R是正则语言。
证明语言CR是上下文无关的。
b．利用a证明语言
A={w|w{a,b,c}*,且含有数目相同的a,b,c}
证明：
a.设P=（Q1,,,1,q1,F1）是一个识别C的PDA，N=（Q2,,2,q2,F2）是识别R的一台NFA。
下面构造识别CR的PDA如下S=（Q,,,,q0,F）:
1）Q=Q1×Q2,是状态集，
2）q0=（q1,q2）是起始状态，
3）F=F1×F2,是接受状态集，
4）是转移函数，满足对任意qQ1,rQ2,a,b,
（（q,r）,a,b）={（（q’,r’）,c）|q’1（q,a）,（r’,c）2（r,a,b）}.
b.Aa*b*c*={anbncn|n0},若A是上下文无关的，则由a中命题知{anbncn|n0}也是上下文无关的，矛盾。
2.26证明：
设G是一个Chomsky范式CFG，则对任一长度2的字符串wL（G）,w的任何派生恰好有2n－1步。
证明：
（用数学归纳法）当n=2时，对于Chomsky范式CFG，长度为2的字符串必由3步派生，此时命题为真。
假设当2nk时命题为真。
当n=k+1时，对于长度为k+1的字符串s=s1s2sk+1，存在S0的一个直接派生S0AB，使得A产生子串s1s2sp，B产生子串sp+1sp+2sk+1，其中1pk+1。
由归纳假设，A产生子串s1s2sp需要2p-1步派生，而B产生子串sp+1sp+2sk+1需要2（k+1-p）-1步派生。
因此，S0产生字符串s共需2（k+1）-1步派生。
即当n=k+1时命题亦真。
因此，由G产生长度为n2的字符串需要2n-1派生。
2.30用泵引理证明下述语言不是上下文无关的：
a.{0n1n0n1n|n0}
假设语言上下文无关，设p为泵长度，取S=0p1p0p1p.由泵引理知，S可以划分为uvxyz且满足泵引理条件。
考察子串vxy,首先，它一定横跨S的中点，否则，若vxy位于S的前半段，由于|vxy|p,则uv2xy2z中1将是后半段字符串的第一个字符，即不可能是0n1n0n1n的形式。
同理，vxy也不可能位于S后半段的位置上。
但是,若vxy跨越S的中点时，将S抽取成uxz，它形如0p1i0j1p,i，j不可能都为p，即uxz不可能是0n1n0n1n的形式。
综上，可知S不能被抽取，因此，该语言不是上下文无关的。
b.{0n#02n#03n|n0}
假设语言上下文无关，设p为泵长度，取S=0p#02p#03p,由泵引理知，S可以划分为uvxyz且满足泵引理条件。
考察子串vxy。
首先，v,y中不能有#，否则S抽取成uxz后，其中#个数1。
由条件3，vxy或者位于第2个#之前，或者位于第1个#之后。
下面讨论这两种情况：
1．此时，uv2xy2z中第3部分0的个数保持不变，而前面部分的0的个数至少有一个增加，因此，uv2xy2z不在该语言中。
2．此时，uv2xy2z中第1部分0的个数保持不变，而第2，3部分0的个数至少有一个增加，也有uv2xy2z不在该语言中。
因此，该语言不是上下文无关的。
c.{w#x|w,x{a,b}*,w是x的子串}
假设该语言上下文无关，设p为泵长度，取S=0p1p#0p1p,由泵引理知，S可以划分为uvxyz且满足泵引理条件。
显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。
子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。
子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。
现在假设#x，则必存在不全为0的i,j，使得vy=1i0j，下面分两种情况考虑：
1．j0,则uxz=0p1p-i#0p-j1p不在该语言中
2．j=0,则uv2xy2z中#左侧的字符串长度大于右边，不在该语言中。
因此，该语言不是上下文无关的。
d.{x1#x2##xk|k2,每一个xi{a,b}*,且存在xi＝xj}
假设该语言上下文无关，设p为泵长度，取S=apbp#apbp,由泵引理知，S可以划分为uvxyz且满足泵引理条件。
显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。
子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。
子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。
于是vxy跨越#两侧.此时，S经抽取成uxz后，具有apbi#ajbp的形式，其中，i,j不全为p。
因此，uxz不在该语言中。
综上该语言不是上下文无关的。
2.34考虑语言B=L（G）,其中G是练习3.13中给出的文法。
定理3.19关于上下文无关语的泵引理称存在关于B的泵长度p。
p的最小值等于多少？
要求给出证明。
证明：
p的最小值为4。
令D={0i#0j#0k|i,j,k0},E={0i#02i|i0},则L（G）=DE。
L（G）中长度为1的字符串仅有#,不能被抽取。
L（G）中长度为2的字符串仅有#,也不能被抽取。
D中长度3的字符串必含有0，所以一定可以被抽取。
E中长度3的字符串也可以被抽取（E中没有长度等于3的字符串）。
只需令uvxyz分别为v=0,x=#,y=00,u,z为两边其余的字符串即可。
注意到此时|vxy|＝4。
但是泵长度不能等于3。
因为若p=3，则要求|vxy|3，但是对于E中的字符串来说，每在#左边抽取1个0，则同时必须在#右边抽取2个0，即|vy|3，又x必须包含#,所以任何有效的抽取必有|vxy|4。
综上所述，p的最小值为4。
2.35设G是一个含有b个变元的乔姆斯基范式CFG。
证明：
如果G产生某个字符串使用了至少2b步的派生，则L（G）是无穷的。
证明：
设G产生字符串S需要至少2b步。
由于一个分支点（变元）对应一次派生，所以S的语法树τ至少有2b个分支点。
又由于在乔姆斯基范式下，一个分支点至多有两个子分支点（这意味着层数n的结点个数2b－1），从而τ的由分支点组成的子树的高度大于等于b+1。
τ有一条路径上分支点（变元）个数b+1。
由鸽巢原理：
必有某个变元R在该路径上出现至少两次。
不妨假设R出现在路径上最下面的b+1个变元中。
按上图所示，将S划分为uvxyz，在每一个R的下面有一棵子树，它产生S的一部分。
上面的R有一棵较大的子树，产生vxy，下面的R有一棵较大的子树，产生x，由于这两棵子树由同一个变元产生，因而可以相互替换。
这里采用如下操作：
反复用较大子树去替换较小子树，则我们得到对于任意n>1,uvnxynzL（G）。
所以若我们能证明v,y不全为ε，则L（G）是无穷的。
事实上，由乔姆斯基范式的特点，上面一个R的派生选择的必为RAB形式的规则，而且不可能有A
和B
，所以v,y不全为。
从而命题得证。
2.26给出一个语言，它不是上下文无关的、但满足泵引理的三个条件。
要求给出证明。
解：
令A＝{aibjckdl|i,j,k,l0,且当i=1时，j=k=l}，则：
（1）A满足泵引理的三个条件。
取泵长度p＝1。
对A中任意长度大于1的字符串s=aibjckdl，分情况可以如下抽取：
若i=1,则j=k=l,取v=a,uxy=，z=bjcjdj,则对n0，uvnxynz=aibjcjdjA；
若i2，且j,k,l不同时为0，不妨设j0，取u=ai,v=b,xy=，z=bj-1ckdl,则对n0，uvnxynz=aibj-1+nckdlA；
若i2，且j=k=l=0,取u=ai-1,v=a,xyz=,则对n0，uvnxynz=ai-1+nA；
若i=0，则j,k,l不同时为0，不妨设j0，取v=b,uxy=，z=bj-1ckdl,则对n0，uvnxynz=bj-1+nckdlA。
（2）A不是上下文无关语言。
事实上，若A为上下文无关语言，另取正则语言R=ab*c*d*，由问题3.17可知，LR是上下文无关的。
但这与LR={abncndn|n0}不是一个上下文无关语言矛盾。
因此，A不是上下文无关的。
升级会员 