发布时间 : 星期三 文章3、上下文无关语言练习更新完毕开始阅读
如果它们总是一样的，并且当输入结束时栈是空的，则接受；否则拒绝。 g. 空集
S→S
3.6 给出产生下述语言的上下文无关文法：
a． 字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。
答：S→bSaSaS|aSbSaS|aSaSbS|?
b． 语言{anbn|n?0}的补集。见问题3.25中的CFG:
答：分析问题：{anbn|n?0}语言的CFG为：S→aSb|?。违反条件的情况可能有两种：
1. 一种是在连续的a中间插入了字符b，或者在连续的b中间插入了字符a。 2. a和b的数目不相等。 所以可以设计文法如下： S→aSb|bT|Ta T→aT|bT|?
// 只能生成错序的或者a和b个数不相等的字符串。 // 生成所有由a,b组成的字符串。
c．{w#x | w, x?{0,1}*且wR是x的子串}。
答： 分析问题：根据题义，语言w#x可以分解成为：
Rw#Tw? ?????TTU其中T是所有由0,1组成的字符串。 所以可以设计文法如下： S→UT U→0U0|1U1|#T T→0T|1T|?
// 生成w#TwR
// 生成所有由0，1组成的字符串
d．{x1#x2#?#xk|k?1, 每一个xi?{a,b}* , 且存在i和j使得xi＝xjR}。 答： 分析问题：根据题义，语言x1#x2#?#xk可以分解成为：
x1#...#xi?1#xRj#...#xj#xj?1#...#xk
???????????????????UVW所以可以设计文法如下： S→UVW
5
U→A#U|? W→#AW|? A→aA|bA|? V→aVa|bVb|#U
3.7 略。
3.8 证明在3.1节开始部分给出的文法G2中，字符串the girl touches the boy with the flower有两个不同的最左派生，叙述这句话的两个不同意思。 G2如下：
＜句子＞→＜名词短语＞＜动词短语＞
＜名词短语＞→＜复合名词＞|＜复合名词＞＜介词短语＞ ＜动词短语＞→＜复合动词＞|＜复合动词＞＜介词短语＞ ＜介词短语＞→＜介词＞＜复合名词＞ ＜复合名词＞→＜冠词＞＜名词＞
＜复合动词＞→＜动词＞|＜动词＞＜名词短语＞ ＜冠词＞→a_|the_
＜名词＞→boy_|girl_|flower_ ＜动词＞→touch_|1ikes_|Sees_ ＜介词＞→with_
答：
// 生成所有由a，b组成的字符串xi
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. 第二种最左派生
6
<句子>?<名词短语><动词短语>?<复合名词><动词短语>?<冠词><名词><动词短语> ?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|AB U?aUb|? V?cV|? A?aA|? B?bBc|?
// 产生aibj，i=j // 产生ck // 产生ai // 产生bjck，j=k
这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生： S?UV?aUbV?abV?abcV?abc S?AB?aAB?aB?abBc?abc
3.10 给出识别3.9中语言A的下推自动机的非形式描述。 解：其非形式描述为：
此PDA有两个非确定性的分支：
1. 读输入中的符号a，把一个a推入栈。同时非确定性地读b，每读一个b从栈中弹出一
个a，若栈中没有a则拒绝。当栈为空时进入接受状态。继续读输入符号，每读一个c，不改变栈内容和状态，若读入a或b则拒绝。
2. 读输入中的符号a，不改变栈内容。当读到b时，将一个b推入栈，同时非确定性地读
c，每读一个c从栈中弹出一个b，若栈中没有b则拒绝。当栈为空时进入接受状态。 如果输入串结束时，一个非确定性分支在接受状态则接受，否则拒绝。
7
3.13 设有上下文无关文法G:
S?TT|U T?0T|T0|# U?0U00|#
a. 用普通的语言描述L(G)。 b. 证明L(G)不是正则的。 答：
S?TT|U T?0T|T0|# U?0U00|#
// 产生所有由0和一个# 组成的字符串
// 产生由0和# 组成的字符串，且符号# 右边的0的个数是左 边的0的个数的二倍。
a. L(G) = {0i#0j#0k | i, j, k?0}∪{0i#02i | i?1}。
c. 假设是正则的。令p是泵引理给出的泵长度，取s为字符串0#0。由于s是L(G)
的一个成员且长度大于p，泵引理保证s可以分成3段s=xyz, 使得对于任意的i?0，xyiz在L(G)中。
根据泵引理的条件3：|xy|?p，则y一定只由0组成，从而字符串xyyx=0所以xyyx?L(G)。矛盾，故L(G)不是正则的。
3.14 用定理3.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。
A?BAB|B|? B?00|? 答：
1) 添加新起始变元S0,
S0?A A?BAB|B|? B?00|? 2) 删除 ? 规则B??
S0?A
A?BAB|AB|BA|A|B|?
8
p+1
p
2p
#0，
2p