计算理论习题答案CHAP2new

3.3 修改定理3.10以得到推论3.12的证明，即证明一个语言是可判定的当且仅当有非确定的TM判定它。

证明：若M是一个确定型判定器则，则M也是一个非确定型判定器。

现在设N是一个非确定的判定器，将构造一个与之等价的确定型判定器M。

模拟过程使用深度搜索。

设N的不确定性分支的最大个数为b。

M有三个带：一个输入带，一个工作带，一个地址带。

M按深度优先方式搜索N的不确定计算分支树。

M= “输入w，1)初始化，第一带上为w, 第二带为空，第三带为1;2)将第一带的内容复制到第二带上，3)按当前地址位数字选择N的一个不确定性分支，在第二带上模拟N运行一步；4)若当前地址位为i<b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为i+1, 转第2步；5)若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为空格, 左移并将当前地址位改为空格直到找到一个地址位其值<b，将当前地址位改为i+1, 转第2步；若到了地址带的最左端仍有当前地址位为b，则拒绝；6)若N进入接受状态，则接受；否则，右移一格，将空格上写入1，转第三步。

”由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停机。

3.4给出枚举器的形式定义。

解：枚举器E=(Q,∑,Γ,δ,q0,qaccept,qreject), 其中转移函数δ为：δ：Q×Γ→Q×Γ×{L,R}×∑*δ (q,a)=(r,b,s1,c)表示若E处于状态q,且在工作带上读到a，则状态转移为r，当前格改写为b并按s1作相应左或右移，打印带上写下字符串c，其中若c等于ε，则不打印。

另外E的起始格局只能是qv，这里v表示一个空格。

3.5检查图灵机的形式定义，回答下列问题并解释你的推测：a．图灵机能在它的带子上写下空白符吗b．带字母表Γ和输入字母表∑能相同吗？c．图灵机的读写头能在连续的两步中处于同一个位置吗？d．图灵机能只包含一个状态吗？解：a．能。

计算理论答案ch2Undergraduate Course ELEMENTS OF COMPUTATION THEORY College of Computer Science Chapter2ZHEJIANG UNIVERSITYFall-Winter,2006P602.1.1Let M be a deterministic?nite automaton.Under exactly what cir-cumstances is e∈L(M)?Prove your answer.Solution:e∈L(M)if and only if s∈F.Suppose e∈L(M).Then,by de?nition of L(M),(s,e) ?M(q,e),where q∈F.Because it is not the case that(s,e) M(q,w)for any con?guration(q,w)(w=e).(s,e) ?M(q,e)must be in the re?exive transitive closure of M by virtue of re?exivity ?that is,(s,e)=(q,e).Therefore,s=q and thus s∈F.Suppose s∈F.Because ?M is re?exive,(s,e) ?M(s,e).Because s∈F,we havee∈L(M)by de?nition of L(M).2.1.2Describe informally the languages accepted by the following DF A.Solution:(c)All strings with the same number of a s and b s and inwhich no pre?x has more thantwo b s than a s,or a s than b s.(d)All strings with the same number of a s and b s and in which no pre?x has more thanone more a than b,or vice-versa.2.1.3Construct DF A accepting each of the following languages.(c){w∈{a,b}?:w has neither aa nor bb as a substring}.(e){w∈{a,b}?:w has both ab and ba as a substring}.Solution:(c)M=(K,Σ,δ,sF),whereK={q0,q1,q2,q3},Σ={a,b},s=q0,F={q0,q1,q2}q aδ(q,a)q0a q1q0b q2q1a q3q1b q2q2a q1q2b q3q3a q3q3b q3(e)M=(K,Σ,δ,sF),whereK={q0,q1,q2,q3,q4,q5},Σ={a,b},s=q0,F={q5}q aδ(q,a)q0a q1q0b q2q1a q1q1b q3q2a q4q2b q2q3a q5q4a q4q4b q5q5a q5q5b q5P742.2.2Which regular expression for the languages accepted by the NF A of Problem2.2.1.Solution:a)a?b)a(ba∪baa)?(b∪ba)2.2.6(a)Find a simple NF A accepting(ab∪aab∪aba)?.(b)Convert the NF A of part(a)to a DF A by the method in section2.2.Solution:(a)M=(K,Σ,?,sF),where K={q0,q1,q2,q3},Σ={a,b},s=q0,F={q0}(qσq i)(q0a q1)(q1a q2)(q1b q0)(q1b q3)(q2a q0)(q3b q0)(b)Determinizing the above machine results in the following DFA:K={{q0},{q1},{q3},{q0,q1},{q0,q2},{q1,q3},?},Σ={a,b},s={q0},F={{q0},{q0,q1},{q0,q2}}{q}σ{δ(q,σ)}{q0}a{q1}{q0}b?{q1}b{q0,q2}{q0,q2}a{q0,q1}{q0,q2}b?{q0,q1}a{q1,q3}{q0,q1}b{q0,q2}{q3}a?{q3}b{q0}{q1,q3}a{q3}{q1,q3}b{q0,q2}a?b?2.2.10Describe exactly what happens when the construction of this sectionapplied to a F A that is already deterministic.Solution:Only |K |of the 2|K |states of the new automaton will be reachable.Each of these states will have {q }for some q ∈K .If we identify {q }with q ,we have a bijection between the states of the old automata and the reachable states of the new one.With respect to this bijection,δ,s ,and F will be identical between the old mach-ine and the new.Sinceis the same,there is a natural isomorphism between the old and the automaton formed from the new one by discarding unreachable states.P 83-842.3.4Using the construction in the proof of theorem 2.3.1,construct F A accepting these languages.(b )((a ∪b )?(e ∪c )?)?.Solution:(b )Ommited.2.3.7Apply the construction in Example 2.3.2to obtain regular expressions responding to each of the F A above.Simplify the resulting regular expres-sions as much as you can.Solution:(a )a ?b (ba ?b ∪a )?(b )((a ∪b )(a ∪b ))?(c )(a ∪b )?abaa (a ∪b )?(d )(a ∪??)(ba ?a )?b (b ∪a )?P 902.4.5Using the pumping theorem and closure under intersection,show that the following are not regular.(a ){ww R :w ∈{a,b }?}Solution:Assume L is regular,by the closure property under intersection so is L 1=L ∩a ?bba ?.Consider language L 1.Let k be the constant whose existence the pumping theorem guarantees.Choose string w =a k bba k ∈L 1.Clearly |w |≥k .So the pumping theorem must hold.Let w =xyz such that |xy |≤k and y =e ,then y =a i where i >0.But then xy n z =a k +(n ?1)i bba k ,which is clearly asymmetric for any n =1.The theorem fails,and thus that L 1is not regular,therefore L is not regular.2.4.8Are the following statements true od false?Explain you answer in each case.(a )Every subset of a regular language is regular.(b )Every regular language has a regular proper subset.(c )If L is regular,then so is {xy |x ∈L and y ∈L }.(d ){w |w =w R }is regular.(e )If L is regular,then so is {w |w ∈L and w R ∈L }.(f )If C is any set of regular languages,then ∪C is a regular language.(g ){xyx R |x,y ∈Σ?}is regular.Solution:(a )False.Every language,including those we know not to be regular,is a subset of theregular language.(b )False.The empty set,which is a regular language,has no proper subsets at all,so it certainly cannot have a proper subset which is also a regular.(c )True.{xy |x ∈L and y ∈L }=L ?ˉL.Since L is regular,so is its complement,and thus their concatenation is regular.(d )False.This can be shown by trying to pump the string a k ba k .y will have to consist only of a s and the resulting xy 2z will unbalanced.Note,however,that this language is regular over an alphabet of one symbol.(It is true when C is required to be ?nite).(e )True.This language is L ∩L R .If L is regular,then so is L R .Since both L and L R are regular,so is their intersection.Solution:(f)False.Any language can be written as the(possibly in?nite)union of the singleton sets containing its individual elements.Since not every language is regular,this claim is false.(g)True.{xyx R|x,y∈Σ?}=Σ?.By letting x=e,y can vary over all the stringsofΣ?.)。

第一章1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题.a.M1的起始状态是q1b.M1的接受状态集是{q2}c.M2的起始状态是q1d.M2的接受状态集是｛q1，q4｝e.对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1f.M1接受字符串aabb吗？否g.M2接受字符串ε吗？是1.2 给出练习2.1中画出的机器M1和M2的形式描述.M 1=(Q1,Σ,δ1,q1,F1) 其中1）Q1={q1,q2,q3,};2）Σ={a,b}; 3）δ1为：4）q1是起始状态5）F1={q2}M2=(Q2,Σ,δ2,q2,F2) 其中1）Q2={q1,q2,q3,q4};2）Σ={a,b}; 3）δ2为：3）q2是起始状态4）F 2={q 1,q 4}1.3 DFA M 的形式描述为 ( {q 1，q 2，q 3，q 4，q 5}，{u,d},δ,q 3，{q 3}),其中δ在表2-3中给出。

试画出此机器的状态图。

1.6 画出识别下述语言的DFA 的状态图。

a){w | w 从1开始以0结束}b){w | w 至少有3个1}c) {w | w 含有子串0101}d) {w | w 的长度不小于3，且第三个符号为0}e) {w | w 从0开始且为奇长度，或从1开始且为偶长度}或f) {w | w 不含子串110}g) {w | w 的长度不超过5}1个1}k) {ε,0}0,11l) {w | w 含有偶数个0，或恰好两个1}m) 空集n) 除空串外的所有字符串1.7 给出识别下述语言的NFA a. {w | w 以00结束}，三个状态b. 语言｛w | w 含有子串0101，即对某个x 和y ，w=x0101y ｝，5个状态.c. 语言｛w | w 含有偶数个0或恰好两个1｝，6个状态。

d. 语言｛0｝，2个状态。

e.语言0*1*0*0，3个状态。

f. 语言{ε}，1个状态。

2.2 a. 利用语言A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例3.20，证明上下文无关语言在交的运算下不封闭。

b. 利用(a)和DeMorgan 律(定理1.10)，证明上下文无关语言在补运算下不封闭。

证明：a.先说明A,B 均为上下文无关文法，对A 构造CFG C 1S →aS|T|ε T →bTc|ε对B,构造CFG C 2S →Sc|R|ε R →aRb由此知 A,B 均为上下文无关语言。

但是由例3.20, A ∩B={a nb nc n|n ≥0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。

b.用反证法。

假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ，A ,B也为CFL ，且CFL 对并运算封闭，所以B A ⋃也为CFL ，进而知道BA ⋃为CFL ，由DeMorgan 定律B A ⋃＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论矛盾，所以CFL 对补运算不封闭。

2.4和2.5 给出产生下述语言的上下文无关文法和PDA ，其中字母表∑={0,1}。

a. {w | w 至少含有3个1}S →A1A1A1A A →0A|1A|ε0, ε→εb. {w | w 以相同的符号开始和结束}S →0A0|1A1 A →0A|1A|εc. {w | w 的长度为奇数}S →0A|1A A →0B|1B|ε B →0A|1Ad. {w | w 的长度为奇数且正中间的符号为0}S →0S0|1S1|0S1|1S0|0e. {w | w 中1比0多}S →A1A0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε 0,ε→0 0,0→εA →0A1|1A0|1A|AA|εf. {w | w=w R }S →0S0|1S1|1|0g. 空集S →S2.6 给出产生下述语言的上下文无关文法：a ．字母表{a,b}上a 的个数是b 的个数的两倍的所有字符串组成的集合。

5.1 证明EQ CFG 是不可判定的。

解：只须证明ALL CFG ≤m EQ CFG 即可。

构造CFG G 1，使L(G 1)=∑*。

设计从ALL CFG 到EQ CFG 的归约函数如下： F=“对于输入＜G ＞，其中G 是CFG ：1）输出＜G ,G 1＞。

”若＜G ＞ALL CFG ，则<G ,G 1>EQ CFG 。

若＜G ＞ALL CFG ，则<G , G 1>EQ CFG 。

F 将ALL CFG 归约到EQ CFG 即ALL CFG ≤m EQ CFG∵ALL CFG 是不可判定的，∴EQ CFG 是不可判定的。

5.2证明EQ CFG 是补图灵可识别的。

证明：注意到A CFG ={<G,w>|G 是能派生串w 的CFG}是可判定的。

构造如下TM ： F=“输入<G ,H>，其中G ,H 是CFG ，1) 对于字符串S 1, S 2,，重复如下步骤。

2) 检测S i 是否可以由G 和H 派生。

3) 若G 和H 中有一个能派生w ，而另一个不能，则接受。

”F 识别EQ CFG 的补。

5.3 略。

5.4 如果A m B 且B 是正则语言，这是否蕴涵着A 也是正则语言？为什么？ 解：否。

例如：对非正则语言A={0n 1n |n 0}和正则语言B={0}，可以构造一个可计算函数f 使得：f(w)=⎩⎨⎧≠=n n nn 10w 1,10w 0, 于是w A f(w)B,故A m B 。

5.5 证明A TM 不可映射规约到E TM 。

证明：反证法假设A TM m E TM ， 则有TM m TM E A ≤。

而A TM 的补不是图灵可识别的，从而可知E TM 的补也不是图灵可识别的。

下面构造一个识别E TM 的补的图灵机S ：S=“输入<M>，M 是TM,1) 对i=1,2,…重复下一步。

2) 对S 1,S 2,…,S i 模拟M 运行i 步，若有接受，则接受。

计算理论习题答案计算理论，也称为理论计算机科学，是研究算法和计算过程的数学理论基础的学科。

以下是一些计算理论习题的答案示例：1. 确定性图灵机（Deterministic Turing Machine, DTM）：- 习题：证明一个确定性图灵机可以模拟任何其他确定性图灵机。

- 答案：确定性图灵机可以读取输入，根据当前状态和读取到的符号，按照预定的转移规则移动磁带头并改变状态。

要模拟另一台确定性图灵机，只需要将被模拟机的状态转移表编码为模拟机的转移规则即可。

2. 非确定性图灵机（Nondeterministic Turing Machine, NTM）：- 习题：证明非确定性图灵机比确定性图灵机更强大。

- 答案：非确定性图灵机可以在多个可能的转移中选择，这使得它能够解决一些确定性图灵机无法解决的问题，例如哈密顿回路问题。

此外，任何确定性图灵机都可以被一个非确定性图灵机模拟，但反之则不成立。

3. 可计算性（Computability）：- 习题：证明某个特定的函数是可计算的。

- 答案：要证明一个函数是可计算的，需要展示一个算法或图灵机，它对于该函数的任何输入都能在有限步骤内给出输出。

例如，一个简单的加法函数f(x, y) = x + y是可计算的，因为它可以通过迭代或递归来实现。

4. 不可解问题（Undecidable Problems）：- 习题：解释停机问题（Halting Problem）为什么是不可解的。

- 答案：停机问题是不可解的，因为它涉及到预测一个图灵机是否会在有限步骤内停止。

如果存在一个算法能够解决停机问题，那么我们可以构造一个悖论，即一个图灵机可以模拟自身并决定自己是否会停止，这会导致自指的悖论。

5. 复杂性类（Complexity Classes）：- 习题：区分P类问题和NP类问题。

- 答案：P类问题是指可以在多项式时间内解决的问题，而NP类问题是指可以在多项式时间内验证一个解的问题。

计算理论期末试题及答案一、单选题1. 下列哪个不是计算理论的基本组成部分？A. 数据结构B. 算法设计C. 编程语言D. 计算机体系结构答案：C2. 在计算理论中，最常用的数据结构是什么？A. 数组B. 链表C. 栈D. 队列答案：A3. 在计算理论中，最佳的算法设计原则是什么？A. 简单原则B. 高效原则C. 美观原则D. 随机原则答案：B4. 下列哪个不是计算机体系结构中的传统计算机组成部分？A. 内存B. CPUC. 硬盘D. 输入输出设备答案：C5. 在计算理论中，最常用的编程语言是什么？A. C++B. JavaC. PythonD. JavaScript答案：C二、多选题1. 下列哪些属于计算理论研究的内容？（可多选）A. 数据处理B. 网络安全C. 数据传输D. 数据压缩答案：A、D2. 下列哪些属于常见的算法设计方法？（可多选）A. 贪心算法B. 动态规划C. 回溯算法D. 辗转相除法答案：A、B、C三、简答题1. 请简要解释什么是递归算法？答案：递归算法是一种直接或间接调用自身的算法。

它通过将一个问题分解成更小的相同问题来解决整个问题，直到达到递归终止条件为止。

2. 请简述数组和链表的区别。

答案：数组是一种线性数据结构，元素在内存中连续存储，通过下标访问元素。

链表也是一种线性数据结构，元素在内存中不连续存储，通过指针连接各个节点。

四、应用题1. 请设计一个算法，计算斐波那契数列的第n项。

答案：以下是使用递归算法解决的斐波那契数列问题的示例代码：```int fibonacci(int n) {if (n <= 1) {return n;}return fibonacci(n - 1) + fibonacci(n - 2);}```2. 请设计一个算法，将一个给定的字符串反转。

答案：以下是使用双指针算法解决字符串反转问题的示例代码：```void reverseString(char* s, int length) {int start = 0;int end = length - 1;while (start < end) {char temp = s[start];s[start] = s[end];s[end] = temp;start++;end--;}}```以上是计算理论期末试题及答案的部分内容，希望对您有所帮助。

计算理论答案汇总第⼀章练习1.1 图给出两台DFA M 1和M 2的状态图. 回答下述有关问题.a. M 1的起始状态是q 1b. M 1的接受状态集是{q 2}c. M 2的起始状态是q 1d. M 2的接受状态集是｛q 1，q 4｝e. 对输⼊aabb,M 1经过的状态序列是q 1，q 2，q 3，q 1，q 1f. M 1接受字符串aabb 吗？否g. M 2接受字符串ε吗？是1.2 给出练习2.1中画出的机器M 1和M 2的形式描述.M 1=(Q 1,Σ,δ1,q 1,F 1) 其中1）Q 1={q 1,q 2,q 3,};2）Σ={a,b};3415）F 1={q 2}M 2=(Q 2,Σ,δ2,q 2,F 2) 其中1）Q 2={q 1,q 2,q 3,q 4};2）Σ={a,b};3324）F 2={q1,q 4}1.3 DFA M 的形式描述为 ( {q 1，q 2，q 3，q 4，q 5}，{u,d},δ,q 3，{q 3}),其中δ在表2-3中给出。

试画出此机器的状态图。

db){w | w ⾄少有3个1}c) {w | w 含有⼦串0101}d) {w | w 的长度不⼩于3，且第三个符号为0}e) {w | w 从0开始且为奇长度，或从1开始且为偶长度}或f) {w | w 不含⼦串110}g) {w | w 的长度不超过5}h){w | w 是除11和111以外的任何字符}i){w | w 的奇位置均为1}j) {w | w ⾄少含有2个0，且⾄多含有1个1}k) {ε,0}l) {w | w 含有偶数个0，或恰好两个1}m) 空集 n) 除空串外的所有字符串1.7 给出识别下述语⾔的NFA ，且要求符合规定的状态数。

a. {w | w 以00结束}，三个状态b. 语⾔｛w | w 含有⼦串0101，即对某个x 和y ，w=x0101y ｝，5个状态. 1c. 语⾔｛w | w 含有偶数个0或恰好两个1｝，6个状态。

第1章概述习题(答案)一．选择题1. D2. B3. CD4. C5. ABC6. A7. B8. B9. ABCD 10. ABCDE二．简答题1．什么是计算机系统？计算机系统是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和存储的系统，由计算机硬件系统和计算机软件系统两大部分组成。

2．请解释冯•诺依曼所提出的“存储程序”概念。

把程序和数据都以二进制的形式统一存放在存储器中，由机器自动执行。

不同的程序解决不同的问题，实现了计算机通用计算的功能。

3．控制器的主要功能是什么？控制器基本功能就是从内存中取出指令和执行指令，即控制器按程序计数器指出的指令地址从内存中取出该指令进行译码，然后根据该指令功能向有关部件发出控制命令，执行该指令。

另外，控制器在工作过程中，还要接受各部件反馈回来的信息。

4．简述CPU和主机的概念。

通常把运算器、控制器做在一个大规模集成电路块上称为中央处理器，又称CPU(Central Processing Unit)。

通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由CPU与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入/输出设备，外存储器等。

5．什么是计算机软件？计算机软件的分类有哪些？软件是指用来指挥计算机运行的各种程序的总和以及开发、使用和维护这些程序所需的技术文档。

计算机软件系统分为系统软件和应用软件。

计算机系统软件由操作系统、语言处理系统、以及各种软件工具等组成，指挥、控制计算机硬件系统按照预定的程序运行、工作，从而达到预定的目标。

应用软件是用户利用计算机软、硬件资源为解决各类应用问题而编写的软件，包括用户程序及其说明性文件资料。

6．计算机有哪些主要的特点？(1)运算速度快、精度高计算机的字长越长，其精度越高，现在世界上最快的计算机每秒可以运算几十万亿次以上。

一般计算机可以有十几位甚至几十位(二进制)有效数字，计算精度可由千分之几到百万分之几，是任何计算工具所望尘莫及的。

计算理论习题解答练习1.1 图给出两台DFA M 1和M 2的状态图. 回答下述有关问题.a. M 1的起始状态是q 1b. M 1的接受状态集是{q 2}c. M 2的起始状态是q 1d. M 2的接受状态集是｛q 1，q 4｝e. 对输入aabb,M 1经过的状态序列是q 1，q 2，q 3，q 1，q 1f. M 1接受字符串aabb 吗？否g. M 2接受字符串ε吗？是1.2 给出练习2.1中画出的机器M 1和M 2的形式描述.M 1=(Q 1,Σ,δ1,q 1,F 1) 其中 1） Q 1={q 1,q 2,q 3,}; 2） Σ={a,b}; 3） δ1为：a b q 1 q 2 q 3 q 2 q 1 q 3 q 3 q 2 q 1 4） q 1是起始状态 5） F 1={q 2}M 2=(Q 2,Σ,δ2,q 2,F 2) 其中 1） Q 2={q 1,q 2,q 3,q 4}; 2） Σ={a,b}; 3）δ2为：a b q 1 q 2 q 3 q 4 q 1 q 2 q 3 q 4 q 2 q 1 q 3 q 4 3） q 2是起始状态 4） F 2={q 1,q 4}1.3 DFA M 的形式描述为 ( {q 1，q 2，q 3，q 4，q 5}，{u,d},δ,q 3，{q 3}),其中δ在表2-3中给出。

试画出此机器的状态图。

1.6 画出识别下述语言的DFA 的状态图。

a){w | w 从1开始以0结束}b){w | w 至少有3个1}q 1 q 5 q 4 q 2 q 3 ud u u u u d d d d 00 1 11 0,1 0 0 1 0 0 1 10,1c) {w | w 含有子串0101}d) {w | w 的长度不小于3，且第三个符号为0}e) {w | w 从0开始且为奇长度，或从1开始且为偶长度}或f) {w | w 不含子串110}g) {w | w 的长度不超过5}h){w | w 是除11和111以外的任何字符}i){w | w 的奇位置均为1}j) {w | w 至少含有2个0，且至多含有1个1}k) {ε,0}l) {w | w 含有偶数个0，或恰好两个1}0,110 0 1 110 0,1 00,1 0,1 1 1 0,1 0 0,10,1 0,1 00,11 0,10 0,1 10,1 0111 00,1 0,1 0,1 0,1 0,10,10,11 1 1 0,1 0 0 00 0 10 0 1 11 1 1 0 0 0,1 0 0,1 0,11 1 00,1 0,1 1 01 1 0 0 0 0 0 0 1m) 空集 n) 除空串外的所有字符串1.7 给出识别下述语言的NFA ，且要求符合规定的状态数。

计算理论答案汇总第一章练习1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题.a. M1的起始状态是q1b. M1的接受状态集是{q2}c. M2的起始状态是q1d. M2的接受状态集是｛q1，q4｝e. 对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1f. M1接受字符串aabb吗？否g. M2接受字符串ε吗？是1.2 给出练习2.1中画出的机器M1和M2的形式描述.M1=(Q1,Σ,δ1,q1,F1) 其中 1）Q1={q1,q2,q3,}; 2）Σ={a,b}; 3）δ1为：a b q1 q2 q1 q2 q3 q3 q3 q2 q1 4）q1是起始状态 5）F1={q2}M2=(Q2,Σ,δ2,q2,F2) 其中 1）Q2={q1,q2,q3,q4}; 2）Σ={a,b}; 3）δ2为： a b q1 q1 q2 q2 q3 q4 q3 q2 q1 q4 q3 q4 3）q2是起始状态 4）F2={q1,q4} 1.3 DFA M的形式描述为 ( {q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。

试画出此机器的状态图。

d d d d u q1 q2 q3 d q4 q5 u u u u1.6 画出识别下述语言的DFA的状态图。

a){w | w从1开始以0结束}11 1 00 00,1b){w | w至少有3个1}0 0 0 0,1c) {w | w含有子串0101} 0,1 1 0 0 0 1 0 11d) {w | w的长度不小于3，且第三个符号为0}0,1 1 00,1 0,1 01 0,1e) {w | w从0开始且为奇长度，或从1开始且为偶长度} 0,10 0 或 0,1 0,1 0,1 0,1 1 10,1f) {w | w不含子串110} 0 1 0,11 1 00 5} g) {w | w的长度不超过0,10,1 0,1 0,1 0,1 0,1 0,1h){w | w是除11和111以外的任何字符}1 1 1 0 0 0 0,1i){w | w的奇位置均为1}10,1 0j) {w | w至少含有2个0，且至多含有1个1} 110 01 1 0,11 0 010 0k) {ε,0} 0 0,1 0,11l) {w | w含有偶数个0，或恰好两个1}1 1 110 0 0 0 0 0 0 0 1 1 1 1m) 空集 n) 除空串外的所有字符串 0,1 0,1 0,11.7 给出识别下述语言的NFA，且要求符合规定的状态数。

8.1 证明对于任意函数f:N N，其中f(n)n，不论用单带TM模型还是用两带只读输入TM模型，所定义的空间复杂性类SPACE(f(n))总是相同的。

证明：为区别，记单带TM模型在f(n)空间内能判定的语言类为SPACE1(f(n)), 而记双带只读输入TM模型在f(n)空间内能判定的语言类为SPACE2(f(n))。

该题要证明的是SPACE1(f(n))＝SPACE2(f(n))。

首先SPACE1(f(n))SPACE2(f(n))。

这是因为设A SPACE1(f(n))，且设M设在f(n)空间内判定A的单带TM，如下构造双带TM只读输入TM N。

N=“对于输入串w：1)将w复制到工作带上。

2)在工作带上模拟M，直到停机。

3)若M接受，则接受；否则，拒绝。

”N在f(n)空间内运行，L(N)=L(M)=A，所以A SPACE2(f(n))。

首先SPACE2(f(n))SPACE1(f(n))。

设A SPACE2(f(n))，且N 为在f(n)空间内判定A的双带只读输入TM。

按照用单带TM模拟多带TM的常规方式构造M：M＝“对于输入串w：1)初始化工作带为＃w1’w2…w n#’.其中以’标记N的两个读写头。

2)模拟N运行直到停机。

每一步模拟，要两次扫描带子。

第一次扫描确定读写头下符号，第二次扫描根据N的转移函数完成改写和移动读写头的工作。

3)若N接受，则接受；否则，拒绝。

”L(M)=L(N)=A。

由于f(n)n，M的运行空间是f(n)+n+2＝O(f(n))。

8.3 考虑广义地理学游戏，其中起始节点就是又无源箭头指入的节点。

选手I有必胜策略吗？选手II呢？给出理由。

1 2 34 5 6I II I II I Winner2 3 6 I4 5 6 II由表上来看选手II有必胜策略I2II4(不能选3)I5II6(不能选2)I。

8.4 证明PSPACE在并、补和星号运算下封闭。

证明：(1) 并：对任意L1, L2PSPACE，设有n a空间图灵机M1和n b空间图灵机M2判定它们，且c=max{a,b}。

计算理论习题解答练习1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题.a.M1的起始状态是q1b.M1的接受状态集是{q2}c.M2的起始状态是q1d.M2的接受状态集是｛q1，q4｝e.对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1f.M1接受字符串aabb吗？否g.M2接受字符串ε吗？是1.2 给出练习2.1中画出的机器M1和M2的形式描述.M1=(Q1,Σ,δ1,q1,F1) 其中1）Q1={q1,q2,q3,};2）Σ={a,b};3415）F1={q2}M2=(Q2,Σ,δ2,q2,F2) 其中1）Q2={q1,q2,q3,q4};2）Σ={a,b};33）q2是起始状态4）F2={q1,q4}1.3 DFA M的形式描述为( {q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。

试画出此机器的状态图。

1.6 画出识别下述语言的DFA 的状态图。

a){w | w 从1开始以0结束}b){w | w 至少有3个1}c) {w | w 含有子串0101}d) {w | w 的长度不小于3，且第三个符号为0}e) {w | w 从0开始且为奇长度，或从1开始且为偶长度}f) {w | w 不含子串110}g) {w | w 的长度不超过5}h){w | w 是除11和111以外的任何字符}i){w | w 的奇位置均为1}j) {w | w 至少含有2个0，且至多含有1个1}k) {ε,0}l) {w | w 含有偶数个0，或恰好两个1}m) 空集 n) 除空串外的所有字符串1.7 给出识别下述语言的NFA ，且要求符合规定的状态数。

0,11a. {w | w以00结束}，三个状态b. 语言｛w | w含有子串0101，即对某个x和y，w=x0101y｝，5个状态.c. 语言｛w | w含有偶数个0或恰好两个1｝，6个状态。