浙江大学计算理论复习总结VIP免费

浙江大学 2 0 1 2 -2 0 1 3 冬学期计算理论重点复习 一个学期的计算理论课程已经结束，给我的感觉吧，计算理论是一门计算机不得不学，学了短期又没用，但是可以培养一些逻辑思维的课程。其最关注的问题是什么是可计算性，什么问题可计算，问题之间的映射/归约，计算代价及难易。在分析问题和检验模型计算能力之前需要掌握的工具是形式语言、图灵机等。本文主要对计算理论中的重点进行了总结，总结了一些定理和理解上容易有障碍的知识点，但是里面还有一些点没有提到，比如 NFA、DFA的相互转化，CFL 和 PDA 的相互转化，需要书中的题目和证明辅助。 Textbook Summary 1. 与自然数集合N 等势 的集合 是可数无 穷 的，称 有穷 的 or 可数无 穷 的集合 是可数的。非可数的集合 称 作 不可数的。 2. DFA ( K, Σ, s, F, δ ) ； NFA（K, Σ，s，F，Δ） 3. 每 台 NFA 都 有一台 等价的 DFA（method: find closu re） 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. 正 则 语 言 （ 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->a or A->B） 18. 对 任 意 CFL G， 都 可 以 在 多 项 式 时 间 构 造 Chomsky 范 式 G’,使 得 L(G’)=L(G)-(Σ∪ {e}) 19. 没 有 chomsky 范 式 能 够 表 示 length<2 的 字 符 串 ， ...