《计算理论》复习题1、设语言A=｛w|w含有子串0101，即对某个x和y，w=x0101y｝，字母表为{0，1}a.画出识别A的DFA的状态图。b.画出识别A的NFA的状态图（规定状态数为5）。0,110011010解:a．010,1010,1b．2、把下图的有穷自动机转换成正则表达式。bab12a解:1、加新的开始状态和新的结束状态bab12asa2、删除状态1，通过状态1的转换有s→1→2、2→1→2a*b2a∪ba*bsa3、删除状态2asa*b(a∪ba*b)*3、设语言A={www|w∈{a,b}*}，利用泵引理证明A不是正则语言。证明：假设A是正则的。设p是泵引理给出的关于A的泵长度。令S=apbapbapb,∵S是A的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。∴A不是正则的。4、证明在3.1节开始部分给出的文法G2中，字符串thegirltouchestheboywiththeflower有两个不同的最左派生，叙述这句话的两个不同的意思。解:G2如下：＜句子＞→＜名词短语＞＜动词短语＞＜名词短语＞→＜复合名词＞|＜复合名词＞＜介词短语＞＜动词短语＞→＜复合动词＞|＜复合动词＞＜介词短语＞＜介词短语＞→＜介词＞＜复合名词＞＜复合名词＞→＜冠词＞＜名词＞＜复合动词＞→＜动词＞|＜动词＞＜名词短语＞＜冠词＞→a_|the_＜名词＞→boy_|girl_|flower_＜动词＞→touch_|1ikes_|Sees_＜介词＞→with_答：第一种最左派生<句子><名词短语><动词短语><复合名词><动词短语><冠词><名词><动词短语>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含义是：女孩碰这个带着花的男孩第二种最左派生<句子><名词短语><动词短语><复合名词><动词短语><冠词><名词><动词短语>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={WcWR|W∈{a,b}*∪c}，请给出这台PDA的形式定义、状态图，并非形式地描述它的运行。6、设语言A={0n1n0n1n|n≧0}，利用泵引理证明A不是上下文无关的。证明：假设A是上下文无关的。设p是泵引理给出的关于A的泵长度。令字符串S=0p1p0p1p,∵S是A的一个成员且S的长度大于p，所以泵引理保证S可被分成5段S=uvxyz且满足泵引理的3个条件。字串vxy一定横跨S的中点，否则，如果vxy位于S的前一半，把S抽成uv2xy2z时，1移到后一半的第一个位置，因此uv2xy2z不可能是A的成员。如果vxy位于S的后一