计算理论课程总结及重点知识点

计算理论复习总结 计算理论是一门计算机不得不学的课程，虽然学了短期又没用，但是可以培养一些逻辑思维的能力。该课程的主要内容是研究什么是可计算性，什么问题可计算，问题之间的映射/归约，计算代价及难易。 在分析问题和检验模型计算能力之前需要掌握的工具是形式语言、图灵机等。以下是计算理论中的重点知识点总结： 1. 可数集合和不可数集合：与自然数集合N等势的集合是可数无穷的，称有穷的or可数无穷的集合是可数的。非可数的集合称作不可数的。 2. DFA和NFA：DFA(K,Σ,s,F,δ)；NFA（K,Σ，s，F，Δ）。每台NFA都有一台等价的DFA（method:findclosure）。 3. 有限自动机和正则语言：有穷自动机接受的语言类=正则语言类（正则表达式描述的语言类）。正则语言在各种运算下封闭。 4. DFA状态最小化：寻找等价类（初始等价类F&K-F）。 5. 上下文无关语法（CFL）：CFL（V，Σ，R，S）。存在非正则的CFL。 6. 推导自动机（PDA）：PDAM=（K，Σ，Γ，Δ，s，F），Γ为栈符号。PDA接受的语言正好是CFL。 7. 泵定理：正则语言（xynz）和CFL（uvnxynz）的泵定理。 8. CFL的例子：L={anbn}∈CFL，L={anbncn}∉CFL但是是递归的，L={an,n为素数}不是CFL。 9. Chomsky范式（CNF）：若R⊆(V-Σ)×V2，则称G=（V，Σ，R，S）为Chomsky范式。 10. 有穷自动机总是停机。 11. CFG到CNF的转化：消除长rules、消除空rules（A->e）、消除短rules（A->aorA->B）。 12. 对任意CFLG，都可以在多项式时间构造Chomsky范式G’,使得L(G’)=L(G)-(Σ∪{e）。 13. 没有chomsky范式能够表示length<2的字符串，所以包含<2的字符串的语言不能转化到chomsky范式。 14. 确定型CFL（确定型PDA接受的语言类）在补下封闭。 15. 图灵机：TM(K，Σ，δ）。 计算理论是一门研究计算机科学的基础课程，涵盖了自动机理论、形式语言、图灵机等领域，旨在培养学生的逻辑思维和问题解决能力。