资源描述：
《上下文无关语言练习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3章、上下文无关语言习题解答-练习3.1回忆一下例3.3中给出的CFGG4。为方便起见，用一个字母重新命名它的变元如下：E→E＋T
2、TT→T×E
3、FF→（E）
4、a给出下述字符串的语法分析树和派生。a.ab.a+ac.a+a+ad.((a))答：a.b.c.d.3.2a.利用语言A={ambncn
5、m,n³0}和B={anbncm
6、m,n³0}以及例3.20(语言B={anbncn
7、n³0}不是上下文无关的)，证明上下文无关语言在交的运算下不封闭。b.利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。证明：a.先说明A,B均为上下文无
8、关文法，对A构造CFGC1S®aS
9、T
10、eT®bTc
11、e//生成bncn对B,构造CFGC2S®Sc
12、R
13、eR®aRb
14、e//生成anbn由此知A,B均为上下文无关语言。由例3.20,A∩B={anbncn
15、n³0}（假设m≤n）不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。9b.用反证法。假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，,也为CFL。因为CFL对并运算封闭，所以也为CFL，进而知道为CFL。由DeMorgan定律，得出是CFL。这与(a)的结论矛盾，所以CFL对补运算不封闭。3.3设上下文无关文法G：R→XRX
16、SS→aTb
17、
18、bTaT→XTX
19、X
20、εX→a
21、b回答下述问题：a.G的变元和终结符是什么？起始变元是哪个？答：变元是：R，X，S，T；起始变元是R。终结符是：a，b，εb.给出L(G)中的三个字符串。答：ab，ba，aab。c.给出不在L(G)中的三个字符串。答：a，b，ε。d.是真是假：。答：假e.是真是假：。答：真f.是真是假：。答：假g.是真是假：。答：假h.是真是假：。答：真i.是真是假：。答：假j.是真是假：。答：真k.是真是假：。答：真l.是真是假：。答：假m.用普通的语言描述L(G)：93.4和3.5给出产生下述语言的上下文无关文法和PDA，其中字母表S={0,1}
22、。a.{w
23、w至少含有3个1}S→A1A1A1AA→0A
24、1A
25、e读输入中的符号。每读一个1，把一个1推入栈，每读1个0，不读栈也不写栈。同时非确定性地转移，并把1个1弹出栈。如果能转移三次，共弹出三个1，则接受这个输入，并继续读输入符号直至结束。否则拒绝这个输入。e,1®e1,e®10,e®ee,1®ee,1®e1,e®e0,e®eb.{w
26、w以相同的符号开始和结束，w的长大于1}S→0A0
27、1A1A→0A
28、1A
29、e读输入中的第一个符号并将其推入栈。继续读后面的符号，同时非确定性地猜想输入符号和栈符号是否相同，如果相同则转移到接受状态，如果此时输入结束，则接受这个输
30、入，否则继续输入。0,e®e1,e®e1,1®e0,0®e0,e®01,e®1c.{w
31、w的长度为奇数}S→ASA
32、0
33、1A→0
34、1读输入中的1个符号，转移到接受状态，再读一个符号，转移到非接受状态，如此循环。可见接受长度为奇数的字符串。0,e®e1,e®e0,e®e1,e®ed.{w
35、w的长度为奇数且正中间的符号为0}S→ASA
36、09A→0
37、1读输入中的1个符号，推入1个0。每当读到0时就非确定性地猜想已经到达字符串的中点，然后变成读输入中的1个符号，就把栈中的0弹出。当输入结束的同时栈被排空，则接受，否则拒绝。1,e®00,e®e0,e®01,0®e0,0®ee,
38、e®$e,$®eb.{w
39、w中1比0多}答：S→T1T
40、T1S//T1T可以产生1比0多1个的所有字符串。//T1S可以产生1比0多2个以上的所有字符串。T→0T1T
41、1T0T
42、ε//T可以产生0和1数目相等的所有字符串。1,e®1e,1®e0,e®0e,1®ee,e®$e,$®e1,0®e0,1®e如果输入0时，栈顶元素是1，则弹出1；否则将0推入堆栈。如果输入1时，栈顶元素是0，则弹出0；否则将1推入堆栈。非确定地猜想栈顶元素是1，且栈中都是1，如果是，则接受；否则拒绝。c.{w
43、w=wR，即w是一个回文，回文是顺读和倒读都一样的字符串}S→0S0
44、1S1
45、1
46、0
47、
48、ε1,e®10,e®e0,e®01,1®e0,0®ee,e®$e,$®e1,e®ee,e®e如果W是回文，那么它的中点有三种可能：1)字符个数是奇数，中点的字符是1。2)字符个数是奇数，中点的字符是0。3)字符个数是偶数，中点的字符是e。9开始时，把读到的字符推入栈中，在每一步非确定性地猜想已经到达字符串的中点。然后变成把读到的每一个字符弹出栈，检查在输入中和在栈顶读到的字符是否一样。如果它们总是一样的，并且当输入结束时栈是空的，则接受；否则拒绝。b.空集S→S3.6给出产生下述语言的上下文无关文法：a．字母表{a,b}上a的个数是b的个数的两倍的
