计算理论模拟试题(3)

计算理论模拟试题

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

含义是： 女孩用花碰这个男孩

5、有自动机M，接受语言L={WcW R | W∈{a,b}*∪c}，请给出这台PDA的形式定义、状态图，并非形式地描述它的运行。

6、设语言A={01 01 | n≧0}，利用泵引理证明A不是上下文无关的。

证明：假设A是上下文无关的。设p是泵引理给出的关于A的泵长度。

令字符串S=01 01,

∵S是A的一个成员且S的长度大于p，所以泵引理保证S可被分成5段S=uvxyz且满足泵引理的3个条件。 字串vxy一定横跨S的中点，否则，如果vxy位于S的前一半，把S抽成uv xy z时，1移到后一半的第一个位置，因此uv xy z不可能是A的成员。如果vxy位于S的后一半，把S抽成uv xy z时，0移到后一半的最后一个位置，因此uv xy z不可能是A的成员。如果字串vxy横跨S的中点，把S抽成u x y，它形如 01 01，其中i和j不可能等于p。于是，S不能被抽取，从而A不是上下文无关的。

p ij p 2 2 2 2 2 2 2 2p pp pn nn n

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库计算理论模拟试题(3)在线全文阅读。