第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