资源描述：
《计算理论模拟试题及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《计算理论》复习题1、设语言A={ww含有子串0101,即对某个兀和y,w=x0101y},字母表为{0,1}a.画出识别A的DFA的状态图ob.画出识别A的NFA的状态图（规定状态数为5）。解：a.b.2、把下图的有穷H动机转换成止则表达式。解：1、加新的开始状态和新的结束状态D2、删除状态1,通过状态1的转换冇s-1-2、2-1-23、删除状态2a*b(aUba"b)*3、设语言A={www
2、we{a,b}*},利用泵引理证明A不是正则语言。证明：假设A是止则的。设卩是泵引理给出的关于A的泵长度。令S=ababab,・・・S是A的一个成员且S的长度大于卩,所以泵引理保证S可被分成3
3、段S=xyz且满足泵引理的3个条件。根据条件3,），屮只含°,所以小w屮第一个。的个数将比后两个a的个数多，故xyyz不是A?的成员。违反泵引理的条件1,矛盾。A不是正则的。4、证明在3」节开始部分给出的文法G2中，字符串thegirltouchestheboywiththeflower有两个不同的最左派生，叙述这句话的两个不同的意思。解:G2如下：V句子>-V名词短语>V动词短语><名词短语>fv复合名词>
4、V复合名词〉V介词短语>V动词短语>fv复合动词>Iv复合动词><介词短语〉<介词短语>Y介词><复合名词>V复合名词〉一V冠词〉V名词〉V复合动词>fV动词>
5、V动词〉V名词短语
6、〉V冠词>fa」the_V名词>-*boy_
7、girl_
8、flowcr_<动词>—touch」1ikes」Sees_<介词>—with_答：1.第一种最左派牛V句子>=<名词短语><动词短语〉=>v复合名词><动词短语>nv冠词><名词><动词短语〉=>a_v名词><动词短语>=>a_girl_v动词短语〉=>a_girl_<复合动词〉=>a_girlv动词〉v名词短语〉=>a_girltouches<名词短语〉=>a_girl_touches_<复合名词X介词短语>=>a_girl_touches_v冠词><名词x介词短语〉girltouchesthev名词><介词名词〉=>agirl
9、touchestheboyv介词短语〉=>agirltouchestheboyV介词><复合名词>=>agirltouchestheboywithv复合名词〉=>a_girl_touches」he_boy_with_v冠词><名词〉=>a_girl_touches_the_boy_with_the_v名词〉=>a_girl_touches_the_boy_with_the_flower含义是：女孩碰这个带着花的男孩2.第二种最左派生<句子〉=>v名词短语><动词短语〉=>v复合名词><动词短语〉=>v冠词><名词X动词短语〉=>a_v名词><动词短语>=>a_girl_<动词短语>=>a
10、_girl_<复合动词><介词短语〉=>a_girl_<动词><名词短语x介词短语>=>a_girl_touchcs_v名词短语><介词知语〉=>a_girl_touches_v冠词><名词><介词短语>=>a_girl_touchcs_the_v名词><介词短语〉=>a_girl_touches_theboy_v介词短语>=>a_girltouchestheboyv介词><复合名词〉=>a_girl_touches_the_boy_with_<复合名词〉=>a_girl_touches_the_boy_with_<冠词><名词〉na_gii*l_touches_the_boy_with
11、_the_v名词〉=>a_girl_touches_the_boy_with_the_flower含义是：一女孩用花碰这个男孩5、有白动机M,接受语言L={WcWR
12、We{a,b}*Uc}，请给出这台PDA的形式定义、状态图，并非形式地描述它的运行。6、设语言A={0nln0nln
13、n^0},利用泵引理证明A不是上下文无关的。证明：假设A是上下文无关的。设"是泵引理给出的关于A的泵长度。令字符串s=opipopip,•・・S是A的一个成员且S的长度人于p,所以泵引理保证S可被分成5段S=uvxyz且满足泵引理的3个条件。字串vxy—定横跨S的中点，否则，如果vxy位于S的前一半，把S抽2
14、222成uvxyz时，1移到后一半的第一个位置，因此uvxyz不可能是A的成员。如果vxy2222位于S的后一半，把S抽成uvxyz吋，0移到后一半的最后一个位置，因此uvxyz不可能是A的成员。如果字串vxy横跨S的中点，把S抽成uxy,它形如0Pl*o'lP,具中i和j不可能等于P。于是，S不能被抽取，从而A不是上下文无关的。7、设语言A={w
15、w至少含有3个1},字母表为{0,1}a.给出产生语言A的上下文无关文法。b.给出产
