计算理论教学资料

1、Textbook Summary1. 与自然数集合N等势的集合是可数无穷的，称有穷的or可数无穷的集合是可数的。非可数的集合称作不可数的。2. DFA( K, , s, F, )；NFA（K,，s，F，）3. 每台NFA都有一台等价的DFA（method:find closure）4. 有穷自动机接受的语言类= 正则语言类（正则表达式描述的语言类）5. 正则语言在各种运算下封闭6. 语言是正则的，iff其等价语言中有有穷个等价类。7. DFA状态最小化-寻找等价类（初始等价类F& K-F）8. CFL（V，R，S）9. 存在非正则的CFL10. 能够生成=两棵语法分析树的字符串的文法叫做歧义的

2、。11. PDAM=（K，s，F），为栈符号12. PDA接受的语言正好是CFL13. 正则语言（xynz）和CFL（uvnxynz）的泵定理14. L=anbnCFL，L=anbncnCFL但是是递归的，L=an,n为素数不是CFL15. Chomsky范式（CNF）：若R(V-)V2，则称G=（V，R，S）为Chomsky范式16. 有穷自动机总是停机。17. CFG到CNF的转化：1) 消除长rules2) 消除空rules（A-e）3) 消除短rules（A-aor A-B）18. 对任意CFLG，都可以在多项式时间构造Chomsky范式G,使得L(G)=L(G)-(e)19. 没有c

3、homsky范式能够表示length2的字符串，所以包含L2的多项式归约，2是L2-L3的多项式归约，则12是L1-L3的多项式归约。44. 证明NP完全：法一、按定义：L*，若（a） LNP，且（b） 对每个语言LNP，存在从L到L的多项式归约则L称为NP完全的。法二、归约，对于语言L，（a） 若LNP（b） 一个NP完全问题可以在多项式时间规约到L，i.e.SAT pL则L称为NP完全的。45. L是NP完全语言，则P=NP，iffLP46. SAT是NP-complete，3-SAT，最大可满足性也是NP完全的47. 覆盖问题，Hamilton圈（有向无向），旅行商问题，背包问题都是NP

4、-complete。48. a*b*c*- anbncn, n 0 is context-free but not regular49. L=L1L2，L是CFL，则L1一定是CFL（）50. Regular-CFL不一定是CFL，如a*b*c*-anbn包含anbncn51. 2-wayPDA(i.e. PDA whose input heads can move both left and right) are more powerfulthan 1-way PDA52. Givena PDA M1 and an FA M2, the problem L(M1) L(M2)is decid

5、able53. DFA/NFA识别的是exactly正则语言。54. R.e.只在补和差下不封闭，CFL在交下也不封闭。55. 非正则语言的*可能是正则语言。比如A:w=wR ,及所有回文，A*=*，为正则语言56. 典型非正则：w=wR57. 正则语言的子集可能非正则，如anbncn,是a*b*c*的子集；又如*是正则语言，H*。58. 归约：X到Y的归约可以理解为X到Y问题的映射,reduction可以解释为at least as difficult as 比如X可以被Y的算法解决，则Xis no more difficult than Y, X可以归约到Y，记XY。e.g. x2可以归约

6、到任意两数的乘积。 若有ArB，A是不可判定问题-B不可判定 A不递归-B不递归B可判定-A可判定 B是递归的-A是递归的59. 若X多项式时间归约到Y，Y多项式时间可解，则X多项式时间可解；若X多项式时间归约到Y，X多项式时间不可解，则Y多项式时间不可解60. X多项式时间归约到Y，Y多项式时间归约到Z，则X多项式时间归约到Z61. PRIME（COMPOSITE）多项式时间归约到Factor，但是Factor多项式时间不能归约到PRIME（COMPOSITE）。62. 若APB，BNP，则ANP。证明：APB存在确定图灵机X，可将A归约到B。BNP 存在一个非确定图灵机N可判定B。我们希望

7、构造一个新的TM（X*N），是的X*N非确定多项式时间求解A，则ANP。Running time of X*N1+p(n)B+q(p(n)(B多项式时间非确定判定)是多项式时间所以ANP63. 若APB，BP，则AP。64. 若X是NPC的，则X在多项式时间内可解iffP=NP.65. SAT多项式时间归约到3-SAT(3-SAT是NPC的)66. 证明语言L是R./R.e./NonR.e.a) Intuitively想想有没有半判定（判定）的TM，有则R.e.(R)。若非R,执行下一步。b) 用能否由R.e.（Non R.e.）语言归约到该语言，能则R.e.而非R（NonR.e）.严格用归约

8、函数定义f：ApB，r1A当且仅当f(r1)Be.g.1 H, iff ML 证明R.e.e.g.2 非H，iffML 证明Non R.e.注意方向：是从A的实例经过递归函数推向B的实例。详细介绍：/nakhleh/COMP481/final_review_sp06_sol.pdf67. 递归与递归等价68. PDA中，若每一个格局至多有一个格局接在它后面，则为确定型的。确定型CFL在补下封闭。69. M半判定L：wL，iff M在w上停机，注意半判定图灵机中不存在“拒绝”状态。只要不接受w，就不停机。70. Chomsky hierarchy71.

9、俩证明：7.6 证明P在并、交、Kleene*连接和补运算下封闭。(1) 并：对任意 L1, L2P，设有na时间图灵机M1和nb时间图灵机M2 判定它们，且c=maxa,b。对L1L2构造判定器M:M=“对于输入字符串w :1) 在w上运行M1，在w上运行M2。2) 若有一个接受则接受，否则拒绝。” 时间复杂度：设M1为O(na),M2为O(nb)。令c=maxa,b。 第一步用时O(na+nb) ，因此总时间为O(na+ nb)=O(nc), 所以L1L2属于P类，即 P在并的运算下封闭。 (2) 连接：对任意 L1, L2属于P 类，设有na时间图灵机M1和nb时间图灵机M2 判定它们，

10、且c=maxa,b。对L1L2 构造判定器M:M=“对于输入字符串w=w1,w2,wn，1) 对k=0,1,2,n重复下列步骤。2) 在w1w2wk上运行M1，在wk+1wk+2wn上运行M2。3) 若都接受，则接受。否则继续。4) 若对所有分法都不接受则拒绝。“ 时间复杂度：(n+1)(O(na)+O(nb)=O(na+1)+O(nb+1)=O(nc+1)，所以L1L2属于P类，即 P在连接的运算下封闭。 (3)补：对任意 L1属于P 类，设有时间O(na)判定器M1判定它，对构造判定器M:M=“对于输入字符串w :(1) 在w上运行M1。(2) 若M1接受则拒绝，若M1拒绝则接受。”时间复

11、杂度为：O(na)。所以属于P类，即 P在补的运算下封闭 。 7.7 证明NP在并和连接运算下封闭。(1) 并：对任意 L1, L2NP，设分别有na时间非确定图灵机M1和nb时间非确定图灵机M2 判定它们，且c=maxa,b。构造判定L1L2的非确定图灵机M:M=“对于输入字符串w :1) 在w上运行M1，在w上运行M2。2) 若有一个接受则接受，否则拒绝。”对于每一个非确定计算分支，第一步用时为O(na)+O(nb)，因此总时间为O(na+nb)=O(nc)。 所以L1L2NP，即 NP在并的运算下封闭。(2) 连接：对任意 L1, L2NP，设分别有na时间非确定图灵机M1和nb时间非确

12、定图灵机M2 判定它们，且c=maxa,b。构造判定L1L2的非确定图灵机M:M=“对于输入字符串w :1) 非确定地将分成两段x,y，使得w=xy。2) 在x上运行M1，在y上运行M2。3) 若都接受则接受，否则拒绝。”对于每一个非确定计算分支，第一步用时O(n),第二步用时为O(na)+O(nb)，因此总时间为O(na+ nb)=O(nc)。 所以L1L2NP，即NP在连接运算下封闭。 专题图灵机可判定性问题判定以下问题是否可判定：声明：思路想证明B问题不可解，1. 从一个不可解问题A入手（如停机问题）2. 创建B的一个实例，从中推出如果能解决B，A也就可以解决了3. 所以B是不可解的1.

13、 一个图灵机有至少481个状态。我们可以给出这样一个TMN进行enc（M），a) 数M中状态数，直到481.b) 如果达到了481，N就接受，否则拒绝。2. 给定图灵机在空串上走了481步还没停机。构造2带图灵机N，a) 2nd 带: 写481个0b) 1st 带在空串上模拟M，每走一步，第2带就删掉一个0c) 如果M在所有0都删掉之后停机，则N接受，否则不接受3. 给定图灵机，判定它是否在一些输入上经过481步还没停机？a) 按字典序找出所有length=481的串xb) 在每个x上面run M，看是否在481步以内停机c) 是则接受，否则reject4. 给定图灵机，判定在所有输入上是否经

14、过481步还没停机？a) 原因同(3)类似5. 给定图灵机是否接受空串？设两个语言：L1= M|M(e)停机；H = |M(w)停机已知H不可判定，只需要找到H-L1的归约即可。令f(“M”,“w”) =M(y) = “M(w)”, M 输入任何y的输出都是M在w上的模拟结果（获得的具体做法是删除任何输入，写入w，再在w上模拟M）。则“M”,”w“H，iffM 在任何串上停机，iff M在空串停机 ML1。6. 给定TM M，是否存在在M上停机的串？给定TM M， M是否在所有上停机的串？设L = M|M(a) where a* ，H = |M(w)停机。寻找H到L的归约。令f(“M”,“w”

15、) =M(y) = “M(w)”, M 输入任何y输出都是M在w上的模拟结果（获得的具体做法是删除任何输入，写入w，再在w上模拟M）。“M”,”w“H，iffM 在任何串上停机，iff M在任何串上停机，iff M在所有a上停机(a*), i.e. ML。7. 给定TM M，is L(M) finite? 设Finite = L(M) where L(M) isfinite; AH = |M accept w存在从AH（非递归）到Finite的递归函数f，f(“M”,“w”)=M(y) = “M(w)”, 显然f可计算。则M,wAH iff M halts on w iff M accept

16、any y*ifff(M,w) is infinite, i.e. M Finite。由于AH归约到Finite，所以Finite非确定，又确定性在补下封闭，所以Finite也是非确定的。8. 给定TM M, 带上是否出现过a（a）？设Write_a = |M有一条在带上写a的规则；AH = |M accept w存在从AH（非递归）到Finite的递归函数f，f(“M”,“w”)=M(“T”,”a”) = Simulate M(w).若M接受w，在带上写a；否则什么也不写。则M,wAH iffM halts on w iffM在带上写了一个aiff f(“M”,“w”)Write_a. 所以

17、Write_a非确定。9. 给定M1，M2，它们是否在一个相同串上停机？设2Halts = |存在令他们都停机的串w；H = |M(w)停机构造新机器M，在M带上写w，模拟M1若停机则清空带，写w，再模拟M2，若M2在w上也停机，则M停机。则有M停机iff2Halt iffH且H。10. 给定M，只要M接受w，M就接受wR 设S = M| M accepts wRwhenever it accept w; AH = |M acceptw递归函数f定义如下，f(M,w)= M(y), 在M上模拟M(w).当M接受w时，create M 只接受串1111；当M拒绝w时，create M只接受串01

18、。则AH iff M接受w iff M只接受1111 iffMS，类似的AHiffM接受01不接受10iffMS判定语言Recursive/Recursive Enumerable / Not R.e.1. L1 = M| there exists an input on which M haltsin less than | steps R.Test on all w less than |M|2. L2 = M| |L(M)|4 Not R.e.a) Reductionfrom H , 说明是R.e.或非R.e.b) 非H，当且仅当M属于L23. L3 = M| |L(M)|2 R.e.

19、not RTextbook Summary1. 与自然数集合N等势的集合是可数无穷的，称有穷的or可数无穷的集合是可数的。非可数的集合称作不可数的。2. DFA( K, , s, F, )；NFA（K,，s，F，）3. 每台NFA都有一台等价的DFA（method:find closure）4. 有穷自动机接受的语言类= 正则语言类（正则表达式描述的语言类）5. 正则语言在各种运算下封闭6. 语言是正则的，iff其等价语言中有有穷个等价类。7. DFA状态最小化-寻找等价类（初始等价类F& K-F）8. CFL（V，R，S）9. 存在非正则的CFL10. 能够生成=两棵语法分析树的字符串的文法

20、叫做歧义的。11. PDAM=（K，s，F），为栈符号12. PDA接受的语言正好是CFL13. 正则语言（xynz）和CFL（uvnxynz）的泵定理14. L=anbnCFL，L=anbncnCFL但是是递归的，L=an,n为素数不是CFL15. Chomsky范式（CNF）：若R(V-)V2，则称G=（V，R，S）为Chomsky范式16. 有穷自动机总是停机。17. CFG到CNF的转化：1) 消除长rules2) 消除空rules（A-e）3) 消除短rules（A-aor A-B）18. 对任意CFLG，都可以在多项式时间构造Chomsky范式G,使得L(G)=L(G)-(e)19

21、. 没有chomsky范式能够表示length2的字符串，所以包含L2的多项式归约，2是L2-L3的多项式归约，则12是L1-L3的多项式归约。44. 证明NP完全：法一、按定义：L*，若（a） LNP，且（b） 对每个语言LNP，存在从L到L的多项式归约则L称为NP完全的。法二、归约，对于语言L，（a） 若LNP（b） 一个NP完全问题可以在多项式时间规约到L，i.e.SAT pL则L称为NP完全的。45. L是NP完全语言，则P=NP，iffLP46. SAT是NP-complete，3-SAT，最大可满足性也是NP完全的47. 覆盖问题，Hamilton圈（有向无向），旅行商问题，背包问

22、题都是NP-complete。48. a*b*c*- anbncn, n 0 is context-free but not regular49. L=L1L2，L是CFL，则L1一定是CFL（）50. Regular-CFL不一定是CFL，如a*b*c*-anbn包含anbncn51. 2-wayPDA(i.e. PDA whose input heads can move both left and right) are more powerfulthan 1-way PDA52. Givena PDA M1 and an FA M2, the problem L(M1) L(M2)is

23、decidable53. DFA/NFA识别的是exactly正则语言。54. R.e.只在补和差下不封闭，CFL在交下也不封闭。55. 非正则语言的*可能是正则语言。比如A:w=wR ,及所有回文，A*=*，为正则语言56. 典型非正则：w=wR57. 正则语言的子集可能非正则，如anbncn,是a*b*c*的子集；又如*是正则语言，H*。58. 归约：X到Y的归约可以理解为X到Y问题的映射,reduction可以解释为at least as difficult as 比如X可以被Y的算法解决，则Xis no more difficult than Y, X可以归约到Y，记XY。e.g. x

24、2可以归约到任意两数的乘积。 若有ArB，A是不可判定问题-B不可判定 A不递归-B不递归B可判定-A可判定 B是递归的-A是递归的59. 若X多项式时间归约到Y，Y多项式时间可解，则X多项式时间可解；若X多项式时间归约到Y，X多项式时间不可解，则Y多项式时间不可解60. X多项式时间归约到Y，Y多项式时间归约到Z，则X多项式时间归约到Z61. PRIME（COMPOSITE）多项式时间归约到Factor，但是Factor多项式时间不能归约到PRIME（COMPOSITE）。62. 若APB，BNP，则ANP。证明：APB存在确定图灵机X，可将A归约到B。BNP 存在一个非确定图灵机N可判定B

25、。我们希望构造一个新的TM（X*N），是的X*N非确定多项式时间求解A，则ANP。Running time of X*N1+p(n)B+q(p(n)(B多项式时间非确定判定)是多项式时间所以ANP63. 若APB，BP，则AP。64. 若X是NPC的，则X在多项式时间内可解iffP=NP.65. SAT多项式时间归约到3-SAT(3-SAT是NPC的)66. 证明语言L是R./R.e./NonR.e.a) Intuitively想想有没有半判定（判定）的TM，有则R.e.(R)。若非R,执行下一步。b) 用能否由R.e.（Non R.e.）语言归约到该语言，能则R.e.而非R（NonR.e）.

26、严格用归约函数定义f：ApB，r1A当且仅当f(r1)Be.g.1 H, iff ML 证明R.e.e.g.2 非H，iffML 证明Non R.e.注意方向：是从A的实例经过递归函数推向B的实例。详细介绍：/nakhleh/COMP481/final_review_sp06_sol.pdf67. 递归与递归等价68. PDA中，若每一个格局至多有一个格局接在它后面，则为确定型的。确定型CFL在补下封闭。69. M半判定L：wL，iff M在w上停机，注意半判定图灵机中不存在“拒绝”状态。只要不接受w，就不停机。70. Chomsky hierarch

27、y71. 俩证明：7.6 证明P在并、交、Kleene*连接和补运算下封闭。(1) 并：对任意 L1, L2P，设有na时间图灵机M1和nb时间图灵机M2 判定它们，且c=maxa,b。对L1L2构造判定器M:M=“对于输入字符串w :1) 在w上运行M1，在w上运行M2。2) 若有一个接受则接受，否则拒绝。” 时间复杂度：设M1为O(na),M2为O(nb)。令c=maxa,b。 第一步用时O(na+nb) ，因此总时间为O(na+ nb)=O(nc), 所以L1L2属于P类，即 P在并的运算下封闭。 (2) 连接：对任意 L1, L2属于P 类，设有na时间图灵机M1和nb时间图灵机M2

28、判定它们，且c=maxa,b。对L1L2 构造判定器M:M=“对于输入字符串w=w1,w2,wn，1) 对k=0,1,2,n重复下列步骤。2) 在w1w2wk上运行M1，在wk+1wk+2wn上运行M2。3) 若都接受，则接受。否则继续。4) 若对所有分法都不接受则拒绝。“ 时间复杂度：(n+1)(O(na)+O(nb)=O(na+1)+O(nb+1)=O(nc+1)，所以L1L2属于P类，即 P在连接的运算下封闭。 (3)补：对任意 L1属于P 类，设有时间O(na)判定器M1判定它，对构造判定器M:M=“对于输入字符串w :(1) 在w上运行M1。(2) 若M1接受则拒绝，若M1拒绝则接受

29、。”时间复杂度为：O(na)。所以属于P类，即 P在补的运算下封闭 。 7.7 证明NP在并和连接运算下封闭。(1) 并：对任意 L1, L2NP，设分别有na时间非确定图灵机M1和nb时间非确定图灵机M2 判定它们，且c=maxa,b。构造判定L1L2的非确定图灵机M:M=“对于输入字符串w :1) 在w上运行M1，在w上运行M2。2) 若有一个接受则接受，否则拒绝。”对于每一个非确定计算分支，第一步用时为O(na)+O(nb)，因此总时间为O(na+nb)=O(nc)。 所以L1L2NP，即 NP在并的运算下封闭。(2) 连接：对任意 L1, L2NP，设分别有na时间非确定图灵机M1和n

30、b时间非确定图灵机M2 判定它们，且c=maxa,b。构造判定L1L2的非确定图灵机M:M=“对于输入字符串w :1) 非确定地将分成两段x,y，使得w=xy。2) 在x上运行M1，在y上运行M2。3) 若都接受则接受，否则拒绝。”对于每一个非确定计算分支，第一步用时O(n),第二步用时为O(na)+O(nb)，因此总时间为O(na+ nb)=O(nc)。 所以L1L2NP，即NP在连接运算下封闭。 专题图灵机可判定性问题判定以下问题是否可判定：声明：思路想证明B问题不可解，1. 从一个不可解问题A入手（如停机问题）2. 创建B的一个实例，从中推出如果能解决B，A也就可以解决了3. 所以B是不

31、可解的1. 一个图灵机有至少481个状态。我们可以给出这样一个TMN进行enc（M），a) 数M中状态数，直到481.b) 如果达到了481，N就接受，否则拒绝。2. 给定图灵机在空串上走了481步还没停机。构造2带图灵机N，a) 2nd 带: 写481个0b) 1st 带在空串上模拟M，每走一步，第2带就删掉一个0c) 如果M在所有0都删掉之后停机，则N接受，否则不接受3. 给定图灵机，判定它是否在一些输入上经过481步还没停机？a) 按字典序找出所有length=481的串xb) 在每个x上面run M，看是否在481步以内停机c) 是则接受，否则reject4. 给定图灵机，判定在所有输

32、入上是否经过481步还没停机？a) 原因同(3)类似5. 给定图灵机是否接受空串？设两个语言：L1= M|M(e)停机；H = |M(w)停机已知H不可判定，只需要找到H-L1的归约即可。令f(“M”,“w”) =M(y) = “M(w)”, M 输入任何y的输出都是M在w上的模拟结果（获得的具体做法是删除任何输入，写入w，再在w上模拟M）。则“M”,”w“H，iffM 在任何串上停机，iff M在空串停机 ML1。6. 给定TM M，是否存在在M上停机的串？给定TM M， M是否在所有上停机的串？设L = M|M(a) where a* ，H = |M(w)停机。寻找H到L的归约。令f(“M”,“w”) =M(y) = “M(w)”, M 输入任何y输出都是M在w上的模拟结果（获得的具体做法是删除任何输入，写入w，再在w上模拟M）。“M”,”w“H，iffM 在任何串上停机，iff M在任何串上停机，iff M在所有a上停机(a*), i.e.