上下文无关语言练习.doc

第3章、上下文无关语言习题解答 - 练习3.1 回忆一下例3.3中给出的CFG G4。为方便起见，用一个字母重新命名它的变元如下：EET|TTTE|FF（E）|a给出下述字符串的语法分析树和派生。a. ab. a+ac. a+a+ad. (a)答：a.b.c.d.3.2 a. 利用语言A=ambncn | m,n0和B=anbncm | m,n0以及例3.20(语言B=anbncn | n0不是上下文无关的)，证明上下文无关语言在交的运算下不封闭。b. 利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。证明：a.先说明A,B均为上下文无关文法，对A构造CFG C1SaS|T|eTbTc|e/生成bncn对B,构造CFG C2SSc|R|eRaRb|e/生成anbn由此知 A,B均为上下文无关语言。由例3.20, AB=anbncn|n0（假设mn）不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。b. 用反证法。假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，,也为CFL。因为CFL对并运算封闭，所以也为CFL，进而知道为CFL。由DeMorgan定律，得出是CFL。这与(a)的结论矛盾，所以CFL对补运算不封闭。3.3 设上下文无关文法G：RXRX|SSaTb|bTaTXTX|X|Xa|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)：3.4和3.5 给出产生下述语言的上下文无关文法和PDA，其中字母表S=0,1。a. w | w至少含有3个1 SA1A1A1AA0A|1A|e读输入中的符号。每读一个1，把一个1推入栈，每读1个0，不读栈也不写栈。同时非确定性地转移，并把1个1弹出栈。如果能转移三次，共弹出三个1，则接受这个输入，并继续读输入符号直至结束。否则拒绝这个输入。e,1e 1, e10, eee,1e e,1e 1, ee0, eeb. w | w以相同的符号开始和结束，w的长大于1S0A0|1A1A0A|1A|e读输入中的第一个符号并将其推入栈。继续读后面的符号，同时非确定性地猜想输入符号和栈符号是否相同，如果相同则转移到接受状态，如果此时输入结束，则接受这个输入，否则继续输入。0,ee1,ee1,1e0,0e0,e01,e1c. w | w的长度为奇数SASA|0|1A0|1读输入中的1个符号，转移到接受状态，再读一个符号，转移到非接受状态，如此循环。可见接受长度为奇数的字符串。0,ee1,ee0,ee1,eed. w | w的长度为奇数且正中间的符号为0SASA|0A0|1读输入中的1个符号，推入1个0 。每当读到0时就非确定性地猜想已经到达字符串的中点，然后变成读输入中的1个符号，就把栈中的0弹出。当输入结束的同时栈被排空，则接受，否则拒绝。1,e00,ee0,e01,0e0,0ee,e$e,$ee. w | w中1比0多答：ST1T |T1S/ T1T可以产生1比0多1个的所有字符串。/ T1S可以产生1比0多2个以上的所有字符串。T0T1T | 1T0T | / T可以产生0和1数目相等的所有字符串。1,e1e,1e0,e0e,1ee,e$e,$e1,0e0,1e如果输入0时，栈顶元素是1，则弹出1；否则将0推入堆栈。如果输入1时，栈顶元素是0，则弹出0；否则将1推入堆栈。非确定地猜想栈顶元素是1，且栈中都是1，如果是，则接受；否则拒绝。f. w | w=wR，即w是一个回文，回文是顺读和倒读都一样的字符串S0S0|1S1|1|0|1,e10,ee0,e01,1e0,0ee,e$e,$e1,eee,ee如果W是回文，那么它的中点有三种可能：1) 字符个数是奇数，中点的字符是1。2) 字符个数是奇数，中点的字符是0。3) 字符个数是偶数，中点的字符是e。开始时，把读到的字符推入栈中，在每一步非确定性地猜想已经到达字符串的中点。然后变成把读到的每一个字符弹出栈，检查在输入中和在栈顶读到的字符是否一样。如果它们总是一样的，并且当输入结束时栈是空的，则接受；否则拒绝。g. 空集SS3.6 给出产生下述语言的上下文无关文法：a 字母表a,b上a的个数是b的个数的两倍的所有字符串组成的集合。答：SbSaSaS|aSbSaS|aSaSbS|eb 语言anbn|n0的补集。见问题3.25中的CFG:答：分析问题：anbn|n0语言的CFG为：SaSb|e。违反条件的情况可能有两种：1. 一种是在连续的a中间插入了字符b，或者在连续的b中间插入了字符a。2. a和b的数目不相等。所以可以设计文法如下：SaSb|bT|Ta/ 只能生成错序的或者a和b个数不相等的字符串。TaT|bT|e/ 生成所有由a,b组成的字符串。cw#x | w, x0,1*且wR是x的子串。答：分析问题：根据题义，语言w#x可以分解成为：其中T是所有由0,1组成的字符串。所以可以设计文法如下：SUTU0U0|1U1|#T/ 生成w#TwRT0T|1T|e/ 生成所有由0，1组成的字符串dx1#x2#xk|k1, 每一个xia,b* , 且存在i和j使得xixjR。答：分析问题：根据题义，语言x1#x2#xk可以分解成为：所以可以设计文法如下：SUVWUA#U|e W#AW|eAaA|bA|e/ 生成所有由a，b组成的字符串xiVaVa|bVb|#U3.7 略。3.8 证明在3.1节开始部分给出的文法G2中，字符串the girl touches the boy with the flower有两个不同的最左派生，叙述这句话的两个不同意思。G2如下：句子名词短语动词短语名词短语复合名词|复合名词介词短语动词短语复合动词|复合动词介词短语介词短语介词复合名词复合名词冠词名词复合动词动词|动词名词短语冠词a_|the_名词boy_|girl_|flower_动词touch_|1ikes_|Sees_介词with_答：1. 第一种最左派生a_a_girl_a_girl_a_girl_a_girl_touches_ a_girl_touches_a_girl_touches_a_girl_touches_the_a_girl_touches_the_boy_a_girl_touches_the_boy_a_girl_touches_the_boy_with_a_girl_touches_the_boy_with_a_girl_touches_the_boy_with_the_a_girl_touches_the_boy_with_the_flower含义是 ：女孩碰这个带着花的男孩2. 第二种最左派生a_a_girl_a_girl_a_girl_a_girl_touches_a_girl_touches_a_girl_touches_the_a_girl_touches_the_boy_a_girl_touches_the_boy_a_girl_touches_the_boy_with_a_girl_touches_the_boy_with_a_girl_touches_the_boy_with_the_a_girl_touches_the_boy_with_the_flower含义是： 女孩用花碰这个男孩3.9 给出产生语言A=aibjck| i,j,k0且或者i=j或者j=k的上下文无关文法。你给出的文法是歧义的吗？为什么？解：下面是产生A的一个CFG:SUV|ABUaUb|e/ 产生aibj，i=jVcV|e/ 产生ckAaA|e/ 产生aiBbBc|e/ 产生bjck，j=k这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生：SUVaUbVabVabcVabcSABaABaBabBcabc3.10 给出识别3.9中语言A的下推自动机的非形式描述。解：其非形式描述为：此PDA有两个非确定性的分支：1. 读输入中的符号a，把一个a推入栈。同时非确定性地读b，每读一个b从栈中弹出一个a，若栈中没有a则拒绝。当栈为空时进入接受状态。继续读输入符号，每读一个c，不改变栈内容和状态，若读入a或b则拒绝。2. 读输入中的符号a，不改变栈内容。当读到b时，将一个b推入栈，同时非确定性地读c，每读一个c从栈中弹出一个b，若栈中没有b则拒绝。当栈为空时进入接受状态。如果输入串结束时，一个非确定性分支在接受状态则接受，否则拒绝。3.13 设有上下文无关文法G:STT|UT0T|T0|#U0U00|#a. 用普通的语言描述L(G)。b. 证明L(G)不是正则的。答：STT|U T0T|T0|#/ 产生所有由0和一个# 组成的字符串 U0U00|#/ 产生由0和# 组成的字符串，且符号# 右边的0的个数是左边的0的个数的二倍。a. L(G) = 0i#0j#0k | i, j, k00i#02i | i1。c. 假设是正则的。令p是泵引理给出的泵长度，取s为字符串0p#02p。由于s是L(G)的一个成员且长度大于p，泵引理保证s可以分成3段s=xyz, 使得对于任意的i0，xyiz在L(G)中。根据泵引理的条件3：|xy|p，则y一定只由0组成，从而字符串xyyx=0p+1#02p，所以xyyxL(G)。矛盾，故L(G)不是正则的。3.14 用定理3.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。ABAB|B|eB00|e答：1) 添加新起始变元S0, S0AABAB|B|eB00|e2) 删除 e 规则BeS0AABAB|AB|BA|A|B|eB003) 删除 e 规则Ae, S0A|e/乔姆斯基范式文法允许规则S eABAB|AB|BA|B|BBB004) 删除单一规则ABS0A|eABAB|AB|BA|00|BBB005) 删除单一规则S0A, S0BAB|AB|BA|00|BB|eABAB|AB|BA|00|BBB006) 添加新的变元和规则S0VB|AB|BA|UU|BB|eAVB|AB|BA|UU|BBBUU VBAU03.19 证明：设G是一个Chomsky范式CFG，则对任一长度n1的字符串wL(G), w的任何派生恰好有2n-1步。证明：对字符串长度n使用数学归纳法。归纳基础：当n=1时，对于Chomsky范式CFG，长度为1的字符串必由1步派生，此时命题为真。归纳步骤：假设命题对长度不超过