《形式语言与自动机Chapter 6 练习参考解答》由会员分享，可在线阅读，更多相关《形式语言与自动机Chapter 6 练习参考解答（4页珍藏版）》请在金锄头文库上搜索。
1、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
2、；下推栈中，；下推栈中，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表示当前扫描过的输入串的任何前缀中表示当前扫
3、描过的输入串的任何前缀中 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)=(
4、q1, X X) ；(q0, , Z0)=( q0, ),(q1, , Z0)=( q1, ).Exercise 6.3.2把下面的文法S aAAA 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,
5、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)。参考解答：参考解答：构造构造 CFG G = (V, 0,1, P , S ) ，其中，其中V = S, pZ0p, pZ0q, qZ0p, qZ0q, pXp, pXq, qXp, qXq ;产产生式集合生式集合 P 中包含如下产生式：中包含如下产生式：（1）对应）对应 (q, 1,
6、Z0) = (q, XZ0)的产生式的产生式q Z0q 1qXqqZ0qq Z0q 1qXppZ0qq Z0p 1qXqqZ0pq Z0p 1qXppZ0p（2）对应）对应 (q, 1, X) = (q, XX)的产生式的产生式q Xq 1qXqqXqq Xq 1qXppXqq Xp 1qXqqXpq Xp 1qXppXp（3）对应）对应 (q, 0, X) = (p, X)的产生式的产生式q Xq 0pXqq Xp 0pXp（4）对应）对应 (q, , X) = (q, )的产生式的产生式q Xq （5）对应）对应 (p, 1, X) = (p, )的产生式的产生式pXp 1（6）对应）对应
7、 (p, 0, Z0) = (q, Z0)的产生式的产生式p Z0q 0q Z0qp Z0p 0q Z0p（7）对应开始非终结符）对应开始非终结符 S 的产生式的产生式S qZ0q S qZ0pExercise 6.4.3 可以分三部分来证明定理 6.19：* a) 证明如果 L = N(P)，其中 P 是 DPDA，则 L 具有前缀性质。b) 证明如果 L = N(P)，其中 P 是 DPDA，则存在 DPDA P满足 L = L(P)。*! c) 证明如果 L 具有前缀性质，并且是某个 DPDA P的 L(P)，则存在 DPDA P 满足 L = N(P)。参考解答：参考解答：(b) 对对 P 做如下修改以构造做如下修改以构造 DPDA P ：（1）增加一个新的初始状态）增加一个新的初始状态 q 0和一个初始栈符和一个初始栈符 Z 0，增加转移，增加转移(q 0, , Z 0) = ( q0, Z0) ，其中其中 q0, Z0分别为分别为 DPDA P 的初始状态和初始栈符的初始状态和初始栈符（2）增加一个终止状态）增加一个终止状态 q f，对任何中的状态，对任何中的状态 q 增加转移增加转移(q, , Z 0) = (q f, Z 0) ，
