计算理论模拟试题
3、设语言A={www | w∈{a,b}*}，利用泵引理证明A不是正则语言。
证明：假设A是正则的。设p是泵引理给出的关于A的泵长度。
令S=ababab,
∵S是A的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。
∴A不是正则的。
4、证明在3.1节开始部分给出的文法G2中，字符串the girl touches the boy with the flower 有两个不同的最左派生，叙述这句话的两个不同的意思。
解: G2如下：
＜句子＞→＜名词短语＞＜动词短语＞
＜名词短语＞→＜复合名词＞|＜复合名词＞＜介词短语＞
＜动词短语＞→＜复合动词＞|＜复合动词＞＜介词短语＞
＜介词短语＞→＜介词＞＜复合名词＞
＜复合名词＞→＜冠词＞＜名词＞
＜复合动词＞→＜动词＞|＜动词＞＜名词短语＞
＜冠词＞→a_|the_
＜名词＞→boy_|girl_|flower_
＜动词＞→touch_|1ikes_|Sees_
＜介词＞→with_
答： ppp
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_<复合名词>