湖南大学计算理论引论期末试题2006年秋本科试卷a-答案

2006年秋《计算理论基础》本科生试卷

填空题

1、确定型有穷自动机的形式定义是一个5元组(Q，?，?，q0，F)其中： (1)Q为有穷状态集，（2）?有穷字母表，（3）?(q,a)是转移函数，它的第1个自变量为q?Q，第二个自变量a??，其结果?(q,a)?Q，即为Q×??Q的函数（映射），（4）q0为初始状态(一般只有一个)，（5）F有一些接受状态（可以为多个。

2、非确定型有穷自动机N接受字符串w=b1b2…bm，是指存在状态序列r0,r1,…,rm,且满足：（1）r0=q0；（2）ri+1??(ri,ai+1) (i=0,1,…,m-1)，(3)rm?F。

3、正则表达式的定义是：（1）a??，空串?，空集?均为合法的正则表达式，（2）若R1，R2是正则表达式，则(R1?R2)、R1?R2、R1*均是正则表达式。

4、将正则表达转换成自动机时，先建立单个字符的自动机，再用并、连、星号运算得到复杂正则表达的自动机，而将自动机转换为正则表达式时，需要先建立新开始状态与一个新接受态，在新开始状态与原开始状态之间连上空串边，在原来所有的接受状态与新接受状态间连空串边。

5、对于正则语言A的任意字符串s，当其长度?p（泵长度）时，则一定存在满足|y|>0、|xy|?p分解方式S=xyz，使得任意i?0，xyiz?A。这是正则语言的性质，基于此性质并利用反证法可证明一个语言不是正则语言，这时需要验证满足“|y|>0、|xy|?p”的每种可能分解方式，都不满足“任意i?0，xyiz?A”。

6、非确定型下推自动机PDA接受w=w1w2…wm，是指存在状态序列r0,r1,…,rm，栈字字符串序列s0,s1,…,sm??*，满足：（1）r0=q0,s0=?；（2）(ri+1,b)??(ri,wi+1,a)，其中si=at(此时a为栈顶元素)，si+1=bt(b为当前动作后的栈顶元素)；（3）rm?F,sm=?。

7、Turing机特点：（1）可以从输送带中读出字符，也可以修改输入带中的字符；（2）可沿输入带向右移动直到遇到字符串结束标志为止，也可从右向左移动直到遇到左端标志为止；（3）可以边读写边移动读写头，也可以不读写而单纯移动；（4）如果进入了“接受”状态则停机(不必消耗所有字符)，如果进入了“拒绝”状态也停机，否则一直运行，永不停机。

8、图灵机的形式定义是7元组(Q,?,?,?,q0,qaccept,qreject)，其中：（1）Q为状态集；（2）?为输入字母表，不包括空白符号；（3）?为带字母表，包括?与空格；（4）?：Q???Q???{L,R}，转换函数，第1个自变量的取值范围是Q，第2个自变量的取值范围是?，其值域是一个三元组，第一个分量表示下一个状态，第二个分量表示写入到输入带上的字符，第三个分量表示下一步的位置；（5）q0?Q是初始状态；（6）qaccept?Q是接受状态；（7）qreject?Q拒绝状态，且qreject?qaccept。

9、图灵机M接受字符串w，是指存在一系列的格局C1,C2,…,Ck，使得：（1）C1是M在输入w的起始格局，即C1=q0w；（2）每个Ci确定地产生Ci+1；（3）Ck是接受格局，即从起始格局起，经过有限步后可达到接受格局。

二、简述题

1、每个多带图灵机等价于某台单带图灵机。请参考下图陈述单带图灵机描述多带图灵机的的细节。多带图灵机为M，待的单带图灵机记为S。

1 a b a 2 a,b 3 S a a a - b a - 0 1 0 1 0 -—

#0 1 0 1 0 #a a a #b a # — — — 非形式的描述：

(1)S在自己的带子上按上图所示放入所有字符串；

(2)为了模拟一步移动，S在其带子上从标记左端点的第一个#开始扫描，一直扫到最右端的第k+1个#，以确定虚拟读写头的符号，即确定原来多带的每个读写头的位置。

然后S进行第二次扫描，并根据M的转移函数指示的运行方式来更新带子(即根据多带机M的转移函数，移动每个带子对应的读写头)

(3)任何时候，只要S将某个虚拟读写头向右移动某个#上面，就意味着M已将该虚拟读写头所对应的读写头，移到了其所在带的空白区域上，即以前没有读过的区域上。

即单带S的写头仍可以向右移动，只不过是先将单带的当前位置起到最后的符号整体右移，再让虚拟读写头在当前位置写下空白符。

2、请给出Chomsky范式的定义？将普通范式转换为Chomsky范式的基本步骤？ 解：Chomsky范式是指满足：A?BC（A,B,C为任意变元，B，C不是起始变元），A?a（a是任意的终结符）；S??（允许这种规则存在，即接受空串）；

转换为Chomsky范式的基本步骤为：

(1)添加新的起始变元S0，同时增加规则S0?S； (2)删除所有“A??”(A?起始变元)，A在其他规则的右边每出现一次添加一条删除了A的新规则。

(3)删除所有单规则“A?B”，并针对所有B?u，添加规则A?u (4)整理A?u1u2…uk为A?u1A1,A1?u2A2,?Ak-2?uk-1uk。 A?aiB为A?BiB,Bi?ai, A?Bai为A?BBi,Bi?ai , A?ajai为A?BjBi,Bi?ai ,Bj?aj

三、计算题

1、给出下列机器的形式描述，并给出字符串aaabbb的计算过程，是否接受该字串

b q b a,b q3 ba q1 21 q4 a a

解：Q={q1,q2,q3,q4}，字母表为{a,b}，开始状态为q1,结束状态集为{q4}，转换函数为?(q1,a)=q1，?(q1,b)=q2，?(q2,a)=q2，?(q2,b)=q3，?(q3,a)=q3，?(q3,b)=q4，?(q4,a)=q4，?(q4,b)=q4。

q1 -a- q1 -a- q1 -a- q1 -b- q2 -b- q3 –b- q4，故接受该字符串。

2、将如下的非确定型自动机转换为确定型自动机，并对状态进行最小化处理。

q0 a ? ? q1 b q2 b ? q5 a

a q3 a q4 b 解：E(q0)={q0,q1,q3}，

?({q0,q1,q3},a)={q4}，?({q0,q1,q3},b)={q2,q5}， ?({q4},b)={q5}

?({q2,q5},a)={q3,q5} ?({q2,q5},b)={q4} ?({q5},a)={q5}

?({q3,q5},a)={q4,q5} ?({q4},b)={q5} ?({q4,q5},a)={q5} ?({q4,q5},b)={q5}

b a q5 a q4 q0,q1,q3 b b q2,q5 a q3,q5 a a,b q4,q5 a q1 b q2 b q3 b a q5 q4 a a,b a q6 F={q1,q3,q4,q5,q6},Q-F={q2}

?(F,a)={q2,q4,q6,q5,q5}，由于?(q1,a)=q2?Q-F，故F={q1}?{q3,q4,q5,q6}，{q2} ?(F,b)={q3,q2,q5}，由于?(q3,b)=q2?Q-F，故F={q1}?{q4,q5,q6}?{q3}?{q2}

?({q4,q5,q6},a)={q6,q5,q5}，?({q4,q5,q6},b)={q5}，其结果没有分开，故{q4,q5,q6}不能再分了，故最小的状态集为{q1}?{q4,q5,q6}?{q3}?{q2}，其状态图为：

a q1 b q2 b q3 b a q4 a,b 3、利用教材上证明定理时所用的方法，构建字符串0(0?1)*对应的非确定型自动。

0 0 ? ? ? 0 ? 0 ? ? ? ? 1 1 ? 0 1 ? 1 ? ? ? 4、写出下列自动机对应的正则表达式。 b q1 qs ? qs ? q2 b a,b q3 a q2 a b q1 b q1 b q1 a b a,b q3 a ? q2 (a?b)a a q2 (a?b)b a((a?b)a)* ? q2 qs ? q2

a((a?b)a)*(a?b)b (a((a?b)a)*(a?b)b?b)*a((a?b)a)*

5、构造出文法G=(V,?,R,S) V={S,A,N,V,P}，?={Jim,big,green,cheese,ate} ，R={ S?P V P，P?N|A P, A?big|green，N?cheese|Jim，V?ate}，请给出对应的下推自动机。

qstart ?,??S$ qLoop ?,$?? qaccept ?,S?P V P ?,P?N|A P ?,A?big|green ?,N?cheese|Jim ?,V?ate Jim,Jim?? big,big?? green,green?? cheese,cheese?? ate,ate??

本文来源：https://www.bwwdw.com/article/m432.html