第3章、上下文无关语言习题解答 - 练习
3.1 回忆一下例3.3中给出的CFG G4。为方便起见，用一个字母重新命名它的变元如下：
E→E＋T|T T→T×E|F F→（E）|a
给出下述字符串的语法分析树和派生。 a.
a
b. a+a c.
a+a+a
d. ((a)) 答：
a. b. c. d.
E?T?F?a
E?E?T?T?F?F?a?a?a
E?E?T?E?T?F?T?F?a?F?a?a?a?a?a E?T?F?(E)?(T)?(F)?((E))?((T))?((F))?((a))
3.2 a. 利用语言A={ambncn | m,n?0}和B={anbncm | m,n?0}以及例3.20(语言B={anbncn | n?0}不是上下文无关的)，证明上下文无关语言在交的运算下不封闭。
b. 利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。 证明：
a.先说明A,B均为上下文无关文法，对A构造CFG C1
S?aS|T|? T?bTc|?
对B,构造CFG C2
S?Sc|R|? R?aRb |?
//生成anbn
//生成bncn
由此知 A,B均为上下文无关语言。
由例3.20, A∩B={anbncn|n?0}（假设m≤n）不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。
1
b. 用反证法。
假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，A,B也为CFL。因为CFL对并运算封闭，所以A?B也为CFL，进而知道A?B为CFL。由DeMorgan定律
A?B?A?B，得出A?B是CFL。
这与(a)的结论矛盾，所以CFL对补运算不封闭。
3.3 设上下文无关文法G：
R→XRX|S S→aTb|bTa T→XTX|X|ε X→a|b
回答下述问题：
a. G的变元和终结符是什么？起始变元是哪个？
答：变元是：R，X，S，T；起始变元是R。终结符是：a，b，ε b. 给出L(G)中的三个字符串。答：ab，ba，aab。 c.
给出不在L(G)中的三个字符串。答：a，b，ε。
d. 是真是假：T?aba。答：假 e. f.
是真是假：T?aba。答：真 是真是假：T?T。答：假
**g. 是真是假：T?T。答：假 h. 是真是假：XXX?aba。答：真 i. j.
是真是假：X?aba。答：假 是真是假：T?XX。答：真
****k. 是真是假：T?XXX。答：真 l.
是真是假：X??。答：假
*m. 用普通的语言描述L(G)：
2
3.4和3.5 给出产生下述语言的上下文无关文法和PDA，其中字母表?={0,1}。
a. {w | w至少含有3个1}
S→A1A1A1A A→0A|1A|?
读输入中的符号。每读一个1，把一个1推入栈，每读1个0，不读栈也不写栈。同时非确定性地转移，并把1个1弹出栈。如果能转移三次，共弹出三个1，则接受这个输入，并继续读输入符号直至结束。否则拒绝这个输入。
0, ??? 1, ??1 ?,1?? ?,1?? 0, ??? 1, ??? ?,1?? b. {w | w以相同的符号开始和结束，w的长大于1}
S→0A0|1A1 A→0A|1A|?
读输入中的第一个符号并将其推入栈。继续读后面的符号，同时非确定性地猜想输入符号和栈符号是否相同，如果相同则转移到接受状态，如果此时输入结束，则接受这个输入，否则继续输入。
c. {w | w的长度为奇数}
S→ASA|0|1 A→0|1
读输入中的1个符号，转移到接受状态，再读一个符号，转移到非接受状态，如此循环。可见接受长度为奇数的字符串。
0,???
1,??? 0,??0 0,0?? 1,??1 1,1?? 0,???
1,??? 0,??? 1,???
d. {w | w的长度为奇数且正中间的符号为0}
S→ASA|0
3
A→0|1
读输入中的1个符号，推入1个0 。每当读到0时就非确定性地猜想已经到达字符串的中点，然后变成读输入中的1个符号，就把栈中的0弹出。当输入结束的同时栈被排空，则接受，否则拒绝。
e. {w | w中1比0多}
答：S→T1T | T1S
如果输入0时，栈顶元素是1，则弹出1；否则将0推入堆栈。 如果输入1时，栈顶元素是0，则弹出0；否则将1推入堆栈。
非确定地猜想栈顶元素是1，且栈中都是1，如果是，则接受；否则拒绝。 f. {w | w=wR，即w是一个回文，回文是顺读和倒读都一样的字符串}
S→0S0|1S1|1|0|ε
// T1T可以产生1比0多1个的所有字符串。 // T1S可以产生1比0多2个以上的所有字符串。 // T可以产生0和1数目相等的所有字符串。
0,??0 1,??0 ?,??$ 0,0?? 1,0?? ?,$?? 0,??? T→0T1T | 1T0T | ε
0,1?? 0,??0 1,0?? 1,??1 ?,??$ ?,1?? ?,$?? ?,1?? 0,??0 0,0?? 1,??1 1,1?? 1,??? ?,??$ 0,??? ?,$?? ?,??? 如果W是回文，那么它的中点有三种可能： 1) 字符个数是奇数，中点的字符是1。 2) 字符个数是奇数，中点的字符是0。 3) 字符个数是偶数，中点的字符是?。
开始时，把读到的字符推入栈中，在每一步非确定性地猜想已经到达字符串的中点。然后变成把读到的每一个字符弹出栈，检查在输入中和在栈顶读到的字符是否一样。
4