一个学期的计算理论课程已经结束，给我的感觉吧，计算理论是一门计算机不得不学，学了短期又没用，但是可以培养一些逻辑思维的课程。其最关注的问题是什么是可计算性，什么问题可计算，问题之间的映射/归约，计算代价及难易。在分析问题和检验模型计算能力之前需要掌握的工具是形式语言、图灵机等。本文主要对计算理论中的重点进行了总结，总结了一些定理和理解上容易有障碍的知识点，但是里面还有一些点没有提到，比如NFA、DFA 的相互转化，CFL和PDA的相互转化，需要书中的题目和证明辅助。 Textbook Summary
1.与自然数集合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.存在非正则的CFL
10.能够生成>=两棵语法分析树的字符串的文法叫做歧义的。
11.PDA M=（K，Σ，Γ，Δ，s，F），Γ为栈符号
12.PDA接受的语言正好是CFL
13.正则语言（xy n z）和CFL（uv n xy n z）的泵定理
14.L={a n b n}∈CFL，L={a n b n c n}∉CFL但是是递归的，L={a n,n为素数}不是CFL
15.Chomsky范式（CNF）：若R⊆(V-Σ)×V2，则称G=（V，Σ，R，S）为Chomsky范式
16.有穷自动机总是停机。
17.CFG到CNF的转化：
1)消除长rules
2)消除空rules（A->e）
3)消除短rules（A->a or A->B）
18.对任意CFL G，都可以在多项式时间构造Chomsky范式G’，使得L(G’)=L(G)-(Σ∪{e})
19.没有chomsky范式能够表示length<2的字符串，所以包含<2的字符串的语言不能转化
到chomsky范式。
20.确定型CFL（确定型PDA接受的语言类）在补下封闭。
21.TM (K，Σ，δ，s，H)，注意字母表Σ不包含←和→
23.如果对于所有w属于Σ*，M(w) = f(w)，我们说M计算函数f，若存在TM计算f，则f
称为递归的。tpa
24.半判定语言的TM都不是算法
25.多带、多带头、双向无穷带or多维带的TM，其判定or半判定的任何语言及任何函数，
都分别可用标准TM判定、半判定or计算。
26.非确定型TM：一个格局可在一步里产生多个其他格局，NDTM is no more powerful than original TM
27.若非确定型TM M半判定或者判定语言L，或者计算函数f，则存在标准型TM M’半判定or判定L，or计算函数f。
28.文法是CFG的推广，任何CFG都是文法。G=（V，Σ，R，S）
29.语言被文法生成iff它是r.e.的。
30.所有数值函数都是原始递归的
31.原始递归函数集是递归可枚举的。
32.特殊语言/问题：
H = {“M””w”: M在w上停机}
非洲猪瘟最新动态
﹁H = { “M””w”：M是一台在”w”上不停机的TM }
H1 = {“M”：M在“M”上停机}
﹁H1 = { w：要么w不是一台TM的编码，
要么w是M的编码，M是一台在”M”上不停机的TM } H：r.e. ; H1：r.e.；﹁H, ﹁H1：非r.e. ；2-SAT∈P； SAT∈NP
中航工业航宇救生装备有限公司
33.没有算法的问题称作不可判定的or不可解的，如TM的停机问题
34.证明不可判定：从通用图灵机U通过递归函数归约到L，如果L是递归的则U是递归的。
<若L1非递归，并存在L1到L2的归约，则L2也非递归。
递归函数是Turing Computable的。
35.语言是图灵可枚举的，iff存在枚举它的图灵机。（M通过空格代开始，周期性的经过特
殊状态q来枚举L，任意顺序且可重复）
36.不可判定语言与递归语言互为补集，与r.e.语言有交集。
37.语言是r.e.，iff它是图灵可枚举的；语言是递归的，iff它是以字典序Turing可枚举的。
38.P在并交连接和补运算下封闭，NP在并、连接运算下封闭。若NP在补下封闭，则NP=P。
39.H = {“M””w”: M在最多2|w|步后停机} ∉P
链轮画法40.所有正则语言和所有CFL都属于P
41.NP：
A.机器角度去定义：被多项式界限非确定型图灵机判定的所有语言的类。
B.基于verifier的定义：NP问题上建立的非确定机包含两步：
1)非确定地猜一个解
2)用一个确定的算法判定该解是否为可行解
判定一个给定猜测值是否满足该问题这两个定义是不矛盾的，因为如果一台非确定TM 在多项式时间内可以判定一个非确定选择的输入是否满足，就是基于verifier 的定义。
（可满足性）的算法称作verifier ，一个问题称作NP 问题当且仅当存在一个多项式时间的verifier 。
P 和NP 的区别：
A problem is in P if we can decide them in polynomial time. It is in NP if we can decide them in polynomial time, if we are given the right certificate . 42. 若存在计算函数f 的多项式界限的图灵机M ，则f 称为多项式时间可计算的。 43. 若τ1是L1->L2的多项式归约，τ2是L2->L3的多项式归约，则τ1·τ2是L1->L3的多项式归约。
44. 证明NP 完全： 法一、按定义：L ⊆Σ*，若
（a ） L ∈NP ，且
（b ） 对每个语言L’∈NP ，存在从L’到L 的多项式归约
则L 称为NP 完全的。
医疗机构病历管理规定
法二、归约，对于语言L ，
周佛海
（a ） 若L ∈NP
（b ） 一个NP 完全问题可以在多项式时间规约到L ，i.e. SAT ≤p L 则L 称为NP 完全的。
45. L 是NP 完全语言，则P=NP ，iff L ∈P 46. SAT 是NP-complete ，3-SAT ，最大可满足性也是NP 完全的
47. 覆盖问题，Hamilton 圈（有向无向），旅行商问题，背包问题都是NP-complete 。 48. a*b*c* - {a n b n c n , n ≥ 0} is context-free but not regular
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议