计算理论模拟试题及答案.doc
- 文档编号:4866086
- 上传时间:2023-05-07
- 格式:DOC
- 页数:6
- 大小:79.50KB
计算理论模拟试题及答案.doc
《计算理论模拟试题及答案.doc》由会员分享,可在线阅读,更多相关《计算理论模拟试题及答案.doc(6页珍藏版)》请在冰点文库上搜索。
《计算理论》复习题
1、设语言A={w|w含有子串0101,即对某个x和y,w=x0101y},字母表为{0,1}
a.画出识别A的DFA的状态图。
b.画出识别A的NFA的状态图(规定状态数为5)。
0,1
1
0
0
1
1
0
1
0
解:
a.
0
1
0,1
0
1
0,1
b.
2、把下图的有穷自动机转换成正则表达式。
b
a
b
1
2
a
解:
1、加新的开始状态和新的结束状态
b
a
b
1
2
a
s
a
2、删除状态1,通过状态1的转换有s→1→2、2→1→2
a*b
2
a∪ba*b
s
a
3、删除状态2
a
s
a*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_
答:
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.第二种最左派生
<句子>Þ<名词短语><动词短语>Þ<复合名词><动词短语>Þ<冠词><名词><动词短语>
Þ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的后一半,把S抽成uv2xy2z时,0移到后一半的最后一个位置,因此uv2xy2z不可能是A的成员。
如果字串vxy横跨S的中点,把S抽成uxy,它形如0p1i0j1p,其中i和j不可能等于p。
于是,S不能被抽取,从而A不是上下文无关的。
7、设语言A={w|w至少含有3个1},字母表为{0,1}
a.给出产生语言A的上下文无关文法。
b.给出产生语言A的下推自动机的非形式描述和状态图。
解:
a.S→A1A1A1A
A→0A|1A|e
读输入中的符号。
每读一个1,把一个1推入栈,每读1个0,不读栈也不写栈。
同时非确定性地转移,并把1个1弹出栈。
如果能转移三次,共弹出三个1,则接受这个输入,并继续读输入符号直至结束。
否则拒绝这个输入。
e,1®e
1,e®1
0,e®e
e,1®e
e,1®e
1,e®e
0,e®e
8、检查图灵机的形式定义,回答下列问题并解释你的推理:
a.图灵机能在它的带子上写下空白字符吗?
b.图灵机能只包含一个状态吗?
解:
a.能。
因为空白符属于带字母表G;
B.不能。
因为qaccept¹qreject,至少应有两个状态。
9、证明正则语言类在并运算下封闭。
10、设INFINITEDFA={|A是一个DFA,且L(A)是一个无限语言}。
证明INFINITEDFA是可判定的。
证明:
设计一个判定INFINITEDFA的TMM即可。
M=“对于输入,其中A是一个DFA:
1)按照引理2.32证明中的构造方法,把DFAA转换成等价的正则表达式。
2)扫描正则表达式,如果包含星号运算符*,则接受;否则拒绝。
”。
11、设B是{0,1}上所有无限序列的集合,用对角化方法证明B是不可数的。
证明:
为证明B是不可数的,必须证明在B和N之间不存在对应。
下面用反证法证之。
假设在B和N之间存在对应f,现在的任务是证明它没有应有的性质。
因为它是一个对应,必须能将N的所有元素与B的所有元素进行配对。
如果能找到B中的一个x,它和N中的任何元素都不能配对,则找到了矛盾。
为此,实际构造出这样一个x。
方法如下:
在选择它的每一位数字时,都使得:
x不同于某个无限序列,且此无限序列已与N中的一个元素配对。
这样就能保证x不同于任何已配对的无限序列。
用一个例子来说明这个思路。
假设对应f存在,且设f
(1)=010101…,f
(2)=101010…,f(3)=…等等。
则f将1和010101…配对,将2和101010…配对,依此类推。
要保证对每个n都有x≠f(n)。
为保证x≠f
(1),只要保证x的第一位数字不同于f
(1)=010101…的第一位数字,即不是数字0,令它为1。
为保证x≠f
(2),只要保证x的第二位数字不同于f
(2)=101010…的第一位数字,即不是数字0,令它为1。
以这种方法继续下去,就能够得到x的所有数字。
不难知道,对任意n,x都不是f(n),因为x与f(n)在第n位上不同。
12、设EQCFG={
证明:
设TMR判定EQCFG;如下构造判定的ALLCFGTMS:
S=“对于输入
1)在输入
2)如果R接受,则接受;如果R拒绝,则拒绝。
”
如果R判定EQCFG,则S判定ALLCFG。
但由定理6.10,ALLCFG是不可判定的。
故EQCFG也是不可判定的。
13、证明:
如果A是图灵可识别的,且A≤m,则A是可判定的。
证明:
因为A≤m<=>≤mA且A为图灵可识别的,根据定理6.22,图灵可识别的。
根据5.16,由A和都是图灵可识别的,所以A是可判定的。
14、证明所有的图灵可识别问题都映射可归约到ATM。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 理论 模拟 试题 答案