23. 证明下列语言不是上下文无关语言:
⑴ { anbncm | m≤n };
证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取
ω = apbpcp ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p
⑴ ω2和ω3不可能同时分别包含a和c,因为在这种情况下,有|ω2ω0ω3|>p; ⑵ 如果ω2和ω3都只包含a (b) ,即ω2ω0ω3 = aj (bj ) (j≤p) ,则当i≠1时, ω1ω2iω0ω3iω4中会出现a的个数与b的个数不等;
如果ω2和ω3都只包含c ,即ω2ω0ω3 = cj (j≤p),当i大于1时,ω1ω2iω0ω3iω4中会出现c的个数大于a的个数 (b的个数);
⑶ 如果ω2和ω3分别包含a和b (b和c) ,当i=0时 ω1ω2iω0ω3iω4中会出现a, b的个数小于c的个数（或a,b个数不等） 这些与假设矛盾,故L不是上下文无关语言. ⑵ { ak | k是质数 };
证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取ω
=ak ( k≥p且k≠1 ) ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p ,且
|ω2ω3|=j≥1 ,则当i=k+1时,|ω1ω2iω0ω3iω4|=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j)至少包含因子k且k≠1 ,因此必定不是质数,即ω1ω2iω0ωi
3ω4不属于L.
这与假设矛盾,故L不是上下文无关语言.
⑶ 由 a,b,c 组成的字符串且是含有 a,b,c 的个数相同的所有字符串.
证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取
ω = akbkck (k≥p) ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p ⑴ ω2和ω3不可能同时分别包含a和c,因为在这种情况下,有|ω2ω0ω3|>p; ⑵ 如果ω2和ω3都只包含a (b或c) ,即ω2ω0ω3 = aj (bj或cj ) (j≤p) ,则当i≠1时, ω1ω2iω0ω3iω4中会出现a,b,c的个数不再相等;
ii
⑶ 如果ω2和ω3分别包含a和b (b和c) , ω1ω2ω0ω3ω4中会出现a,b的个数与c的不等;
这些与假设矛盾,故L不是上下文无关语言.
24. 设G是Chomsky 范式文法,存在ω∈ L (G) ，求在边缘为ω的推导树中,最长的路
径长度与ω的长度之间的关系.
解: 设边缘为ω的推导树中,最长路径长度为n,则它与ω的长度之间的关系为|ω|≤2n-1 .
因为由Chomsky范式的定义可知,Chomsky范式文法的推导树都是二叉树,在最长路径长度为n的二叉推导树中,满二叉树推出的句子长度最长,为2n-1,因此ω的长度与其推导树的最长路径长度n的关系可以用上式表示.
25. 设计PDA接受下列语言(注意:不要求为确定的)
⑴ { 0m1n | m≤n };
解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1,qf } ,
T = { 0,1} ,
Г = { 0,1, Z0 } , F = { qf } ,
δ定义如下:
δ( q0, ε, Z0 ) = { ( q1, Z0 ) } , δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } , δ( q0,0,0 ) = { ( q0, 00 ) } , δ( q0,1, Z0 ) = { ( qf,ε ) } , δ( q0,1, 0 ) = { ( q1,ε ) } , δ( q1,1, 0 ) = { ( q1,ε ) } , δ( q1,ε, Z0 ) = { ( qf,ε ) } δ( q1,1, Z0 ) = { ( qf,ε ) } δ( qf,1, ε) = { ( qf,ε ) }
⑵ { 0m1n | m≥n };
解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1,qf } , T = { 0,1} ,
Г = { 0,1, Z0 } , F = { qf } ,
δ定义如下:
δ( q0, ε, Z0 ) = { ( q1, Z0 ) } , δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } , δ( q0,0,0 ) = { ( q0, 00 ) } , δ( q0,1, 0 ) = { ( q1,ε ) } , δ( q1,1, 0 ) = { ( q1,ε ) } , δ( q1,ε,Z0 ) = { ( qf,ε ) } , δ( q1,ε,0 ) = { ( qf,ε ) } δ( qf,1, ε) = { ( qf,ε ) } ⑶ { 0m1n0m | n和m任意 };
解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1, q2,q3,qf } , T = { 0,1} ,
Г = { 0,1, Z0 } , F = { qf } ,
δ定义如下:
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } , δ( q0,0,0 ) = { ( q0, 00 ),( q0,ε)} , δ( q0,1, Z0 ) = { ( q3,ε ) } , δ( q3,1, ε) = { (q3,ε) } , δ( q3,ε, ε) = { ( qf,ε ) } , δ( q0,1,0 ) = { ( q1,0 ) } , δ( q1,1,0 ) = { ( q1,0 ) } , δ( q1,0,0 ) = { ( q2,ε ) } ,
δ( q2,0,0 ) = { ( q2,ε ) } , δ( q2,ε, Z0 ) = { ( qf,ε ) } , δ( q0, ε, Z0 ) = { ( qf, ε)}nm
? 第五章
1. 考虑如下的图灵机 M = ( {q0, q1, qf, },{0,1},{0,1,B},δ, q0,B,{ qf } ),其中δ定义为:
δ(q0,0) = {(q1,1,R)} , δ(q1,1) = {(q0,0,R)} , δ(q1,B) = {(qf,B,R)} , 非形式化但准确地描述该图灵机的工作过程及其所接受的语言.
解: 开始时,M的带上从左端起放有字符串0(10)i (i≥0),后跟无限多个空白符B.M的第一
次动作先读到第一个0,并改写为1;然后右移,如果找到第一个1,则改写为0,并继续向右寻找下一个0,这样重复进行.当向右寻找1的时候,找到一个空白符B,则结束. 该图灵机所接受的语言L(M) = { 0(10)i | i≥
相关推荐：
loading