3、上下文无关语言练习 下载本文

第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