计算理论教学资料.docVIP

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. PDAM=（K，Σ，Γ，Δ，s，F），Γ为栈符号 12. PDA接受的语言正好是CFL 13. 正则语言（xynz）和CFL（uvnxynz）的泵定理 14. L={anbn}∈CFL，L={anbncn}?CFL但是是递归的，L={an,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-aor A-B） 18. 对任意CFLG，都可以在多项式时间构造Chomsky范式G’,使得L(G’)=L(G)-(Σ∪{e}) 19. 没有chomsky范式能够表示length2的字符串，所以包含2的字符串的语言不能转化到chomsky范式。 20. 确定型CFL（确定型PDA接受的语言类）在补下封闭。 21. TM(K，Σ，δ，s，H)，注意字母表Σ不包含←和→ 22. 若存在TM判定L，则称L是递归的。 23. 如果对于所有w属于Σ*，M(w) = f(w)，我们说M计算函数f，若存在TM计算f，则f称为递归的。 24. 半判定语言的TM都不是算法 25. 多带、多带头、双向无穷带or多维带的TM，其判定or半判定的任何语言及任何函数，都分别可用标准TM判定、半判定or计算。 26. 非确定型TM：一个格局可在一步里产生多个其他格局，NDTM is no more powerful than original TM 27. 若非确定型TMM半判定或者判定语言L，或者计算函数f，则存在标准型TMM’半判定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是递归的。 i.e.若L1非递归，并存在L1到L2的归约，则L2也非递归。 递归函数是TuringComputable的。 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) 用一个确定的算法判定该解是否