形式语言与自动机Chapter 6 练习参考解答.docVIP

Chapter 6 练习参考解答 Exercise 6.2.1 设计PDA使它接受下列语言，你可以使用以终结状态方式接受或者以空栈方式接受中方便的一个。 b) 所有由0,1构成的，并且任何前缀中1的个数都不比0的个数多的串的集合。 c) 所有0,1个数相同的0,1串的集合。 参考解答： b) 构造以终态方式接受的PDA P = (Q, Σ, Γ, δ, q0, Z0, F) ，其中 Q={q0}；状态q0表示当前扫描过的输入串的任何前缀中1的个数不比0的个数多； Σ={0，1}； Γ={ Z0，X}；下推栈中，X的个数表示当前扫描过的输入串中0的个数比1的个数多多少； F={q0}； δ(q0,0, Z0)={( q0,X Z0)}, δ(q0,0, X)={( q0,X X)}, δ(q0,1, X)={( q0,()}. c) 构造以空栈方式接受的PDA P = (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,X Z0)}, δ(q0,1, Z0)={( q1,X Z0)}； δ(q1,0, Z0)={( q0,X Z0)}, δ(q1,1, Z0)={( q1,X Z0)}； δ(q0,0, X)={( q0,X X)},δ(q0,1, X)={( q0,()}； δ(q1,0, X)={( q1, ()},δ(q1,1, X)={( q1, X X)} ； δ(q0, (, Z0)={( q0, ()},δ(q1, (, Z0)={( q1, ()}. Exercise 6.3.2 把下面的文法 S ( aAA A ( aS | bS | a 转换成以空栈方式接受同样语言的PDA。 参考解答： 构造以空栈方式接受的PDA P = ({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,()}； Exercise 6.3.3 把PDA P = ({p, q}, {0, 1}, {x, z0}, δ, q, Z0)转化为一个CFG，其中δ为： δ(q, 1, Z0) = {(q, XZ0)}。 δ(q, 1, X) = {(q, XX)}。 δ(q, 0, X) = {(p, X)}。 δ(q, ε, X) = {(q, ε)}。 δ(p, 1, X) = {(p, ε)}。 δ(p, 0, Z0) = {(q, Z0)}。 参考解答： 构造CFG G = (V, {0,1}, P , S ) ，其中 V = {S, [pZ0p], [pZ0q], [qZ0p], [qZ0q], [pXp], [pXq], [qXp], [qXq] }; 产生式集合P中包含如下产生式： （1）对应δ(q, 1, Z0) = {(q, XZ0)}的产生式 [q Z0q] ( 1[qXq][qZ0q] [q Z0q] ( 1[qXp][pZ0q] [q Z0p] ( 1[qXq][qZ0p] [q Z0p] ( 1[qXp][pZ0p] （2）对应δ(q, 1, X) = {(q, XX)}的产生式 [q Xq] ( 1[qXq][qXq] [q Xq] ( 1[qXp][pXq] [q Xp] ( 1[qXq][qXp] [q Xp] ( 1[qXp][pXp] （3）对应δ(q, 0, X) = {(p, X)}的产生式 [q Xq] ( 0[pXq] [q Xp] ( 0[pXp] （4）对应δ(q, (, X) = {(q, ()}的产生式 [q Xq] ( ( （5）对应δ(p, 1, X) = {(p, ()}的产生式 [pXp] ( 1 （6）对应δ(p, 0, Z0) = {(q, Z0)}的产生式 [p Z0q] ( 0[q Z0q] [p Z0p] ( 0[q Z0p] （7）对应开始非终结符S的产生式 S ( [qZ0q] S ( [qZ0p] Exercise 6.4.3 可以分三部分来证明定理6.19