Chapter6练习参考解答Exercise6.2.1设计PDA使它接受下列语言，你可以使用以终结状态方式接受或者以空栈方式接受中方便的一个。b)所有由0,1构成的，并且任何前缀中1的个数都不比0的个数多的串的集合。c)所有0,1个数相同的0,1串的集合。参考解答：b)构造以终态方式接受的PDAP=(Q,Σ,Γ,δ,q0,Z0,F)，其中Q={q0}；状态q0表示当前扫描过的输入串的任何前缀中1的个数不比0的个数多；Σ={0，1}；Γ={Z0，X}；下推栈中，X的个数表示当前扫描过的输入串中0的个数比1的个数多多少；F={q0}；δ(q0,0,Z0)={(q0,XZ0)},δ(q0,0,X)={(q0,XX)},δ(q0,1,X)={(q0,)}.c)构造以空栈方式接受的PDAP=(Q,Σ,Γ,δ,q0,Z0)，其中Q={q0，q1}；状态q0表示当前扫描过的输入串的任何前缀中0的个数不少于1的个数，状态q1表示当前扫描过的输入串的任何前缀中1的个数不少于0的个数；Σ={0，1}；Γ={Z0，X}；下推栈中，X的个数表示当前扫描过的输入串中0的个数比1的个数或1的个数比0的个数多多少；δ(q0,0,Z0)={(q0,XZ0)},δ(q0,1,Z0)={(q1,XZ0)}；δ(q1,0,Z0)={(q0,XZ0)},δ(q1,1,Z0)={(q1,XZ0)}；δ(q0,0,X)={(q0,XX)},δ(q0,1,X)={(q0,)}；δ(q1,0,X)={(q1,)},δ(q1,1,X)={(q1,XX)}；δ(q0,,Z0)={(q0,)},δ(q1,,Z0)={(q1,)}.Exercise6.3.2把下面的文法SaAAAaS|bS|a转换成以空栈方式接受同样语言的PDA。参考解答：构造以空栈方式接受的PDAP=({q},{a,b},{S,A,a,b},δ,q,S)，其中δ(q,,S)={(q,aAA)}；δ(q,,A)={(q,aS),(q,bS),(q,a)}；δ(q,a,a)={(q,)}；δ(q,b,b)={(q,)}；Exercise6.3.3把PDAP=({p,q},{0,1},{x,z0},δ,q,Z0)转化为一个CFG，其中δ为：1.δ(q,1,Z0)={(q,XZ0)}。2.δ(q,1,X)={(q,XX)}。3.δ(q,0,X)={(p,X)}。4.δ(q,ε,X)={(q,ε)}。5.δ(p,1,X)={(p,ε)}。6.δ(p,0,Z0)={(q,Z0)}。参考解答：构造CFGG=(V,{0,1},P,S)，其中V={S,[pZ0p],[pZ0q],[qZ0p],[qZ0q],[pXp],[pXq],[qXp],[qXq]};产生式集合P中包含如下产生式：（1）对应δ(q,1,Z0)={(q,XZ0)}的产生式[qZ0q]1[qXq][qZ0q][qZ0q]1[qXp][pZ0q][qZ0p]1[qXq][qZ0p][qZ0p]1[qXp][pZ0p]（2）对应δ(q,1,X)={(q,XX)}的产生式[qXq]1[qXq][qXq][qXq]1[qXp][pXq][qXp]1[qXq][qXp][qXp]1[qXp][pXp]（3）对应δ(q,0,X)={(p,X)}的产生式[qXq]0[pXq][qXp]0[pXp]（4）对应δ(q,,X)={(q,)}的产生式[qXq]（5）对应δ(p,1,X)={(p,)}的产生式[pXp]1（6）对应δ(p,0,Z0)={(q,Z0)}的产生式[pZ0q]0[qZ0q][pZ0p]0[qZ0p]（7）对应开始非终结符S的产生式S[qZ0q]S[qZ0p]Exercise6.4.3可以分三部分来证明定理6.19：*a)证明如果L=N(P)，其中P是DPDA，则L具有前缀性质。b)证明如果L=N(P)，其中P是DPDA，则存在DPDAP’满足L=L(P’)。*!c)证明如果L具有前缀性质，并且是某个DPDAP’的L(P’)，则存在DPDAP满足L=N(P)。参考解答：(b)对P做如下修改以构造DPDAP：（1）增加一个新的初始状态q0和一个初始栈符Z0，增加转移δ(q0,,Z0)={(q0,Z0)}，其中q0,Z0分别为DPDAP的初始状态和初始栈符（2）增加一个终止状态qf，对任何中的状态q增加转移δ(q,,Z0)={(qf,Z0)}，
