a. {0n1n0n1n | n?0}
pppp
假设语言上下文无关，设p为泵长度，取S=0101.由泵引理知，S可以划分为uvxyz且满足泵引理条件。
22
考察子串vxy,首先，它一定横跨S的中点，否则，若vxy位于S的前半段，由于|vxy|?p, 则uvxyz中1
nnnn
将是后半段字符串的第一个字符，即不可能是0101的形式。同理，vxy也不可能位于S后半段的位置上。
pijpnnnn
但是,若vxy跨越S的中点时，将S抽取成uxz，它形如0101,i，j不可能都为p，即uxz不可能是0101的形式。
综上，可知S不能被抽取，因此，该语言不是上下文无关的。
b. {0n#02n#03n | n?0}
p2p3p
假设语言上下文无关，设p为泵长度，取S=0#0#0, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。考察子串vxy。首先，v,y中不能有#，否则S抽取成uxz后，其中#个数?1。由条件3，vxy或者位于第2个#之前，或者位于第1个#之后。下面讨论这两种情况：
22
①． 此时，uvxyz中第3部分0的个数保持不变，而前面部分的0的个数至少有一个增加，因此，
22
uvxyz不在该语言中。
22
②． 此时，uvxyz中第1部分0的个数保持不变，而第2，3部分0的个数至少有一个增加，也有
22
uvxyz不在该语言中。
因此，该语言不是上下文无关的。 c. {w#x | w,x?{a,b}*, w是x的子串}
pppp
假设该语言上下文无关，设p为泵长度，取S=01#01, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。
22
子串vxy不能落在#的左侧，否则uvxyz中#左侧的字符串长度将大于右边。 子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。 现在假设#?x，则必存在不全为0的i,j，使得vy=1i0j，下面分两种情况考虑：
①． j?0, 则uxz=0p1p-i#0p-j1p不在该语言中 ②． j=0, 则uv2xy2z中#左侧的字符串长度大于右边，不在该语言中。
因此，该语言不是上下文无关的。
d. {x1#x2#?#xk | k?2, 每一个xi?{a,b}*, 且存在xi＝xj}
pppp
假设该语言上下文无关，设p为泵长度，取S=ab#ab, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。
22
子串vxy不能落在#的左侧，否则uvxyz中#左侧的字符串长度将大于右边。 子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。
pijp
于是vxy跨越#两侧.此时，S经抽取成uxz后，具有ab#ab的形式，其中，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, k?0}, E={0i#02i | i?0}, 则L(G)=D?E。
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。
- 21 -
综上所述，p的最小值为4。
2.35 设G是一个含有b个变元的乔姆斯基范式CFG。证明：如果G产生某个字符串使用了至少2b步的派生，则L(G)是无穷的。
T
R 证明：设G产生字符串S需要至少2b步。
由于一个分支点(变元)对应一次派生，所以S的语法树τ至少有2b个分支点。又由于在乔姆斯基范式下，一个分支点至多有两个子分支点(这意味着层数?n
R b
的结点个数?2－1)，从而τ的由分支点组成的子树的高度大于等于b+1。τ有一条路径上分支点(变元)个数?b+1。由鸽巢原理：必有某个变元R在该路
u v x y z
径上出现至少两次。不妨假设R出现在路径上最下面的b+1个变元中。
按上图所示，将S划分为uvxyz，在每一个R的下面有一棵子树，它产生S的一部分。上面的R有一棵较大的子树，产生vxy，下面的R有一棵较大的子树，产生x，由于这两棵子树由同一个变元产生，因而可以相互替换。这里采用如下操作：反复用较大子树去替换较小子树，则我们得到对于任意n>1, uv nxy n
z?L(G)。
所以若我们能证明v,y不全为ε，则L(G)是无穷的。
?事实上，由乔姆斯基范式的特点，上面一个R的派生选择的必为R?AB形式的规则，而且不可能有A??
?和B??，所以v,y不全为?。从而命题得证。
2.26 给出一个语言，它不是上下文无关的、但满足泵引理的三个条件。要求给出证明。 解：令A＝{aibjckdl | i,j,k,l?0, 且当i=1时，j=k=l}，则：
(1) A满足泵引理的三个条件。取泵长度p＝1。对A中任意长度大于1的字符串s= aibjckdl ，分情况可以如下抽取：
若i=1,则j=k=l, 取v=a,uxy=?，z= bjcjdj, 则对?n?0，uvnxynz= aibjcjdj ?A；
若i?2，且j,k,l不同时为0，不妨设j?0，取u=ai,v=b,xy=?，z= bj-1ckdl, 则对?n?0，uvnxynz= aibj-1+nckdl ?A；
若i?2，且j=k=l=0, 取u=ai-1,v=a,xyz=?, 则对?n?0，uvnxynz= ai-1+n?A； 若i=0，则j,k,l不同时为0，不妨设j?0，取v=b,uxy=?，z= bj-1ckdl, 则对?n?0，uvnxynz=bj-1+nckdl ?A。
(2) A不是上下文无关语言。事实上，若A为上下文无关语言，另取正则语言R=ab*c*d*，由问题3.17可知，L?R是上下文无关的。但这与L?R={abncndn | n?0}不是一个上下文无关语言矛盾。因此，A不是上下文无关的。
3.3 修改定理3.10以得到推论3.12的证明，即证明一个语言是可判定的当且仅当有非确定的TM判定它。 证明：若M是一个确定型判定器则，则M也是一个非确定型判定器。 现在设N是一个非确定的判定器，将构造一个与之等价的确定型判定器M。模拟过程使用深度搜索。 设N的不确定性分支的最大个数为b。
M有三个带：一个输入带，一个工作带，一个地址带。M按深度优先方式搜索N的不确定计算分支树。 M= “输入w，
1) 初始化，第一带上为w, 第二带为空，第三带为1;
- 22 -
2) 将第一带的内容复制到第二带上，
3) 按当前地址位数字选择N的一个不确定性分支，在第二带上模拟N运行一步； 4) 若当前地址位为i 转第2步； 5) 若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为空 格, 左移并将当前地址位改为空格直到找到一个地址位其值 6) 若N进入接受状态，则接受；否则，右移一格，将空格上写入1，转第三步。” 由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停机。 3.4 给出枚举器的形式定义。 解：枚举器E=(Q,?,?,?,q0,qaccept,qreject), 其中转移函数?为： ?：Q×??Q×?×{L,R}×?* ? (q,a)=(r,b,s1,c) 表示若E处于状态q,且在工作带上读到a，则状态转移为r，当前格改写为b并按s1作相应左或右移，打印带上写下字符串c，其中若c等于?，则不打印。 另外E的起始格局只能是q0v，这里v表示一个空格。 3.x 检查图灵机的形式定义，回答下列问题并解释你的推测： a． 图灵机能在它的带子上写下空白符吗 b．带字母表?和输入字母表?能相同吗？ c．图灵机的读写头能在连续的两步中处于同一个位置吗？ d．图灵机能只包含一个状态吗？ 解： a．能。因为空白符属于带字母表?； b．不能。因为空白符不属于输入字母表?； c．能。当读写头处于左端点时，如果转移是向左转移，因为不准机器从带的左端点移出，所以下一个格 局读写头仍在左端点。 d．不能。因为qaccept?qreject，至少应有两个状态。 3.6 解：因为M不一定是判定器，可能会在运行某个si时不停机，则L(M)中按字典序大于si的字符串不可能被枚举出来。 3.7 解：因为图灵机的一个本质要求是一步之内，只能做有限的工作，而第1)步中取所有可能的值，这有无限多种情况。 3.8 构造具有3条带的图灵机。 对于问题a. 1) w 先读入第一条带，然后读到0就把0写入第2条带，读到1就把1写入第3条带，直到读到空 格为止。 2) 然后把3个读写头都返回到最左边。 3) 开始读第2条带和第3条带，每次都是读一个字符，如果同时遇上空格符，则接收，否则拒绝。 对于问题b: 1) 和a的第1步相同。 - 23 - 2) 和a的第2步相同。 3) 每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，就接收，否则拒绝。 对于问题c: 1) 和a的第1步相同。 2) 和a的第2步相同。 3) 每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，就拒绝，否则接受。 3.x由题知,1-pda代表一个栈的下推自动机,2-pda代表两个栈的下推自动机。如果能用2-pda模拟一个图灵机,而我们已经知道图灵机比下推自动机强大，那么就有2-pda比1-pda更强大。设有TM S。下面构造2-pda P，且记其两个栈分别为A，B： P＝“对于输入w, 1) 将w读入栈A，再全部从栈A中依次弹出并读入栈B。 2) 模拟S在w上运行。记录S的当前状态，并且栈B的栈顶字符为S的读写头所指方格的字符： a) 若S执行一个右移?(q,a)=(r,b,R)，则将栈B的栈顶字符a替换为b，弹出b，推入栈A，记录 S的当前状态r。 b) 若S执行一个左移?(q,a)=(r,b,L)，首先将栈B的栈顶字符a替换为b；若栈A不空，则将栈A 弹出一个字符推入栈B；若栈A为空(对应于S处于工作带最左端)，则不作栈操作。记录S的当前状态r。 3) 若S进入接受状态，则进入接受状态。” 由上知.我们用2-pda模拟了图灵机,所以2-pda比1-pda强大. 下面用一个四带TM S来模拟一个3-pda P，要求P进入接受状态之前排空栈，并且或者推入或者弹出： 记P的三个栈为A,B,C。S的四个带，第一带用来模拟P的输入带，第二,三,四带分别模拟栈A,B,C： S＝“对于输入字符串w， 1) 初始化，第一带放入w，第二，三，四带为空。 2) 模拟P分别在四个带上按如下方式动作： a． 若P在输入带上读一个非空字符，则读第一带字符并右移一格； 若P在输入带上读一个?，则在第一带上不读字符，且读写头保持不动。 b． 栈A,B,C中若有弹出，则在相应带上当前格改写为空格，并左移一格；若有推入a，则 在相应带上右移一格，并写入a。 3) 若P进入接受状态，则接受。” 3.10证明双无限带图灵机识别图灵可识别语言。 证明思路：利用双无限单带图灵机模拟普通单带图灵机时，只需要设计一个左端点。我们的证明是让它在第一格左边标记“$”作为左端点。 证明： 首先用单带双无限带图灵机模拟普通单带图灵机： 设有普通图灵机M1＝( Q1, ?, ?1, ?1, q0, qaccept, qreject )。 下面构造与之等价的单带双无限带图灵机M2＝( Q2, ?, ?2, ?2, qs, qaccept, qreject )，其中 Q2=Q1?{qs,qt}, qs为新的起始状态；?2＝?1?{$}. 对任意q?Q2, a??2, - 24 - 若 q?qs,?(qt,a,L),?若 q?qt,?(q0,$,R), ?2(q,a)????1(q,a),若 q?Q1 , a??1,??(q, $, R)，若 q?Q1 , a?$.再用普通单带图灵机模拟单带双无限带图灵机： 设有单带双无限图灵机M1＝(Q,?,?,?,q0,qaccept,qreject)，下面构造普通单带图灵机M2： M2=“输入串w， 1) 将带上字符串改写为$w, 将读写头放在w的第一个字符上， 2) 按照M1的转移函数运行， 3) 每当读写头移到了$上，就将$右边的所有字符右移一格，并在$右边的方格里写上空格符，再 将读写头放在这个方格上，转第二步， 4) 若进入接受状态，则接受；若进入拒绝状态则拒绝。” 也可以用普通双带图灵机模拟单带双无限带图灵机： 设有单带双无限图灵机M1＝(Q,?,?,?,q0,qaccept,qreject)，下面构造普通双带图灵机M2： M2=“输入串w， 1) 在第一个带上放上$, 读写头放在$上； 第二个带子上放入#w, 读写头放在第二个方格上。 2) 当第一带读写头位于$上，而第二带读写头不在＃上时，在第二带上按照M1的转移规则运行， 直到停机或读写头移到#上。若进入接受状态则接受，若进入拒绝状态则拒绝。若读写头移到#上，则将第一带上读写头右移一格。 3) 当第二带读写头位于#上，而第一带读写头不在$上时，在第一带上按照M1的转移规则运行， 但是每一步要将读写头移动方向反向，直到停机或读写头移到$上。若进入接受状态则接受，若进入拒绝状态则拒绝。若读写头移到$上，则将第二带上读写头右移一格，转第二步。” 3.11只写一次图灵机是一个单带图灵机，它在每个带方格上最多只能改变其内容一次(包括带上得输入区域)。证明图灵机模型的这个变形等价于普通的图灵机模型。 证明：普通单带图灵机总是可以模拟只写一次图灵机。下面说明怎样用一个只写一次TM T 模拟一个普通单带TM S。 T=“对于输入w=w1w2?wn, 1) 在w1w2?wn上并模拟S运行。 2) 每当S要改写工作带时(例如设S要将当前方格内容改写为b，并且左移或右移一格)，T按如下方 式动作： a. 将当前方格改写为“b*”，在带子右边第一个空格写下“#”。 b. 将“#”左边的字符抄写到“#”右边(注：每抄写一个字符，需要将此格字符改写一次以作上标记，但是“b*”不用再作另外标记，而且将“b*”抄写为“b~”)。 c. 找到带有标记“~”的字符，再模拟S左移或右移一格。 然后继续模拟S。 3) 若S接受则接受；若S拒绝则拒绝。” 3.12 对于普通图灵机N，构造与之等价的带左复位的图灵机E： E＝“对于输入w, 1) 在w上模拟N的一步动作： - 25 -