3、上下文无关语言练习.doc

第3章、上下文无关语言习题解答 - 练习3.1 回忆一下例3.3中给出的CFG G4为方便起见，用一个字母重新命名它的变元如下： E→E＋T|T T→T×E|F F→（E）|a 给出下述字符串的语法分析树和派生a. ab. a+ac. a+a+ad. ((a))答：a.b.c.d.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 C1S®aS|T|eT®bTc|e //生成bncn对B,构造CFG C2S®Sc|R|eR®aRb |e //生成anbn由此知 A,B均为上下文无关语言由例3.20, A∩B={anbncn|n³0}（假设m≤n）不是上下文无关语言，所以上下文无关语言在交的运算下不封闭b. 用反证法假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，,也为CFL。

因为CFL对并运算封闭，所以也为CFL，进而知道为CFL由DeMorgan定律，得出是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，aabc. 给出不在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} S→A1A1A1AA→0A|1A|e读输入中的符号每读一个1，把一个1推入栈，每读1个0，不读栈也不写栈。

同时非确定性地转移，并把1个1弹出栈如果能转移三次，共弹出三个1，则接受这个输入，并继续读输入符号直至结束否则拒绝这个输入e,1®e 1, e®10, e®ee,1®e e,1®e 1, e®e0, e®eb. {w | w以相同的符号开始和结束，w的长大于1}S→0A0|1A1A→0A|1A|e读输入中的第一个符号并将其推入栈继续读后面的符号，同时非确定性地猜想输入符号和栈符号是否相同，如果相同则转移到接受状态，如果此时输入结束，则接受这个输入，否则继续输入0,e®e1,e®e1,1®e0,0®e0,e®01,e®1c. {w | w的长度为奇数}S→ASA|0|1A→0|1读输入中的1个符号，转移到接受状态，再读一个符号，转移到非接受状态，如此循环可见接受长度为奇数的字符串0,e®e1,e®e0,e®e1,e®ed. {w | w的长度为奇数且正中间的符号为0}S→ASA|0A→0|1读输入中的1个符号，推入1个0 每当读到0时就非确定性地猜想已经到达字符串的中点，然后变成读输入中的1个符号，就把栈中的0弹出当输入结束的同时栈被排空，则接受，否则拒绝1,e®00,e®e0,e®01,0®e0,0®ee,e®$e,$®ee. {w | w中1比0多}答：S→T1T | T1S // T1T可以产生1比0多1个的所有字符串。

// T1S可以产生1比0多2个以上的所有字符串 T→0T1T | 1T0T | ε // 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，如果是，则接受；否则拒绝f. {w | w=wR，即w是一个回文，回文是顺读和倒读都一样的字符串}S→0S0|1S1|1|0|ε1,e®10,e®e0,e®01,1®e0,0®ee,e®$e,$®e1,e®ee,e®e如果W是回文，那么它的中点有三种可能：1) 字符个数是奇数，中点的字符是12) 字符个数是奇数，中点的字符是03) 字符个数是偶数，中点的字符是e开始时，把读到的字符推入栈中，在每一步非确定性地猜想已经到达字符串的中点然后变成把读到的每一个字符弹出栈，检查在输入中和在栈顶读到的字符是否一样如果它们总是一样的，并且当输入结束时栈是空的，则接受；否则拒绝g. 空集S→S3.6 给出产生下述语言的上下文无关文法：a． 字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。

答：S→bSaSaS|aSbSaS|aSaSbS|eb． 语言{anbn|n³0}的补集见问题3.25中的CFG:答：分析问题：{anbn|n³0}语言的CFG为：S→aSb|e违反条件的情况可能有两种：1. 一种是在连续的a中间插入了字符b，或者在连续的b中间插入了字符a2. a和b的数目不相等所以可以设计文法如下：S→aSb|bT|Ta // 只能生成错序的或者a和b个数不相等的字符串T→aT|bT|e // 生成所有由a,b组成的字符串c．{w#x | w, xÎ{0,1}*且wR是x的子串}答： 分析问题：根据题义，语言w#x可以分解成为：其中T是所有由0,1组成的字符串所以可以设计文法如下：S→UTU→0U0|1U1|#T // 生成w#TwRT→0T|1T|e // 生成所有由0，1组成的字符串d．{x1#x2#¼#xk|k³1, 每一个xiÎ{a,b}* , 且存在i和j使得xi＝xjR}答： 分析问题：根据题义，语言x1#x2#¼#xk可以分解成为：所以可以设计文法如下：S→UVWU→A#U|e W→#AW|eA→aA|bA|e // 生成所有由a，b组成的字符串xiV→aVa|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,k³0且或者i=j或者j=k}的上下文无关文法。

你给出的文法是歧义的吗？为什么？解：下面是产生A的一个CFG:S®UV|ABU®aUb|e // 产生aibj，i=jV®cV|e // 产生ckA®aA|e // 产生aiB®bBc|e // 产生bjck，j=k这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生：SÞUVÞaUbVÞabVÞabcVÞabcSÞABÞaABÞaBÞabBcÞabc3.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:S®TT|UT®0T|T0|#U®0U00|#a. 用普通的语言描述L(G)b. 证明L(G)不是正则的。

答：S®TT|U T®0T|T0|# // 产生所有由0和一个# 组成的字符串 U®0U00|# // 产生由0和# 。