转一个学长的总结，原文http://chj-yh.i.sohu.com/blog/view/113784360.htm
Contents
第一章 导引
1、如果起始状态也是接受状态，则接受空串 。
2、计算的形式定义：
设M={……}，是一台有穷自动机，w=w0w1……wn是字母表上的一个字符串，如果Q中存在状态序列r0，r1，…. rn，满足以下条件：
r0=q0
（ri，wi+1）=ri+1 ，i=0，1，….，n-1
rn 属于F
则M接受w。
3、正则语言的定义：
如果一个语言能够被一台有穷自动机识别，则称他是正则语言。
4、正则语言的运算封闭性：并，连接，星 。
5、DFA 确定型有穷自动机 NFA 非确定型有穷自动机。
6、费确定型有穷自动机：产生的是下一个状态的集合P（Q）。而DFA是一个状态。
7、DFA和NFA识别相同的语言。能够识别相同的语言则认为是等价的。
8、一个语言是正则的当且仅当可以用正则表达式描述它。
第二章 正则语言
1、自动机的形式定义：5元组，状态集，字母表，转移函数，起始状态，终结状态。
第三章 上下文无关语言
1、上下文无关文法的形式定义。四元组----变元集、终结符集、规则集、起始变元。
2、正则语言与确定性自动机DFA等价。
3、乔姆斯基范式：A—>BC，A—>a，a为任意终结符，A、B、C为变元，其中B、C不能为起始变元，允许S—>空，其中S为起始变元。任意上下文无关语言都可以用乔姆斯基范式产生。
4、CFG转乔姆斯基范式：去空规则，删除变元；处理单一规则，传递增加规则。P65.
5、下推自动机PDA：6元组，状态集、字母表、栈字母表、转移函数、起始状态、终结状态集，与上下文无关文法等价；
6、一个语言是上下文无关的，当且仅当有一台PDA识别他。
7、非上下文无关语言的泵引理：P74。
第四章 丘奇-图灵论题
1、图灵机的形式化定义：7元组。
2、如果有图灵机识别的一个语言，则称这个语言是图灵可识别的。
3、判定器：对所有输入都停机的图灵机。永不循环。总能是拒绝或者接受。
4、图灵可识别的语言不一定都是图灵可判定的。图灵可判定语言都是图灵可识别的。
5、多带图灵机：与单带图灵机等价，虚拟读写头和磁带，相对于单带，用#号将各带子分开。
6、一个语言是图灵可识别的当且仅当有多带图灵机识别他。
7、非确定型图灵机：在任何时刻，机器可以在多种可能性中选择一种继续进行。
8、每个非确定型图灵机都有一个确定型图灵机与之等价。
9、一个语言是可判定的当且仅当有一个非确定性图灵机判定他。
10、枚举器：图解P91。
11、丘奇：那么打演算，图灵：机器判定。
12、图灵机连通图的判定：扫描顶点，做标记，已标记顶点和无标记顶点是否存在边，做标记，扫描所有顶点，决定是接受还是拒绝。
13、0-PDA就是一个NFA，1-PDA就是pda，3PDA不比2PDA强。
第五章 可判定性 停机并相应的进入拒绝或者接受状态
1、与正则语言有关的可判定性问题：
ADFA ：DFA B是否接受w的问题。ADFA是可判定的。ANFA是可判定的。ARES是可判定的。EDFA是可判定的。EQDFA是可判定的。P100。核心思想：图灵机跟踪DFA的状态和当前位置，状态和位置的变化由转移函数决定。
2、与上下文无关语言相关的可判定性问题：
ACFG是一个可判定语言。核心思想：将CFG转换为乔姆斯基文法，w的任意派生都是2n-1步，只需检查2n-1步内的派生，其中n是w的长度。ECFG是可判定的。所有的CFG都是可判定的。
3、停机问题（图灵机进入循环）：
ATM是不可判定的，但确实图灵可识别的（识别不一定能判定，能判定则一定可以识别）。
停机问题是不可判定的，存在无限循环。
4、对角化方法：存在语言是不是图灵可识别的。
5、一个语言是可判定的，当且仅当他既是图灵可识别的，也是补图灵可识别的。即：一个语言是可判定的，当且仅当他和他的补都是图灵可识别的。（消除无限循环）
6、ATM的补不是图灵可识别的。
7、D正，上无P。
第六章 可规约性
1、可规约性：计算上是不可解的问题。规约就是将一个问题转化为另一个问题的方法。
2、HALTTM是不可判定的。核心思想，将其规约到一个图灵机可以判定的问题。构造一个图灵机来判定ATM，得出矛盾。ETM是不可判定的。
3、REGULARTM是不可判定的（M是一个TM，而且其识别的语言是正则语言）。核心思想：
4、赖斯定理：检查关于语言的任何一个性质是否有图灵机识别都是不可判定的。EQTM是不可判定的（核心思想：根据Etm的不可判定性）。
5、LBA：线性界限自动机。不会离开带子的左右端点，TM不会离开带子的左端点。
6、每个CFL都可以用一个LBA判定，ADFA，ACFG，EDFA，ECFG的判定器都是LBA。
7、ALBA是可判定的。ELBA是不可判定的。ALLCFG是不可判定的。PCP（波斯特对应问题）是不可判定的。核心思想：将其规约到ATM是不可判定的。
8、ALBA的格局是有限的，qngn个。Q为状态数，n为带子长度，g为符号数。
9、映射可规约性（上面讲的都是计算历史可规约性）：
10、可计算函数：
11、映射可规约的定义（略）。P124。
12、EQTM既不是图灵可识别的，也不是补图灵可识别的（是不可判定的）。核心思想：
构造ATM到EQTM的映射归约。P125。
第七章 可计算理论的高级专题
第八章 时间复杂性
1、时间复杂度的定义：w的长度的函数f（n）所经过的最大步数。
2、时间复杂性类：略。P149。
3、单带图灵机在o（nlogn）时间内判定的语言都是正则语言。如果是双带图灵机，则可以在O（n）时间内判定。核心思想：复制比较。
4、模型间的复杂性关系：
每一个t（n）时间的多带图灵机都和某个o（t2(n)）的单带图灵机等价。
每一个t（n）的非确定性单带图灵机都与某个2O（t（n））的确定性图灵机等价。
5、P类：是确定型单带图灵机在多项式时间内可以判定的语言类。
PATH是P类问题——核心思想：进行单点标记。
REALPRIME是P类问题——核心思想：欧几里德算法，gcd（x，y）=1。
每一个上下文无关语言是多项式时间可判定的——核心思想：2n-1步推到，动态规划。
6、NP类：是具有多项式时间验证机的语言类。不具备多项式时间解决方法。
验证机：是一个算法，多项式时间算法。
一个语言在NP中，当且仅当它能够被某个非确定型多项式时间图灵机判定。或者是存在验证机在多项式时间内判定。
图中团的判定。子集和问题。
NP《= EXPTIME《= TIME( )
7、NP 完全问题：NP中的某些问题的复杂性与整个类的复杂性相关，这些问题中的任何一个问题如果存在多项式时间算法，那么所有NP问题都是多项式时间可解的，这些问题称为NP完全的。
8、SAT是P，当且仅当P=NP。SAT是NP完全的。
9、多项式时间可规约性：定义见P162。
10、NP完全性的定义：满足两个条件
B属于NP，并且，NP中的每个A都可以多项式时间可规约到B。
11、几个NP完全问题：coNP
团，顶点覆盖，哈密顿回路问题，SAT问题，子集和问题。
补充：
文字：变量或者变量的非。
子句：由或者连接起来的文字。
合取范式（cnf）：由并连接起来的子句。
3cnf：所有的子句都有3个文字。
第九章 空间复杂性问题
1、核心思想：空间可以重用，而时间不能。比如说SAT可以在线性空间内解决。
2、SPACE(f(n))和NSPACE(f(n))。定义略，确定型图灵机和非确定型图灵机判定的语言类。
3、萨维奇定理：任何非确定型TM都可以转化为f2（n）空间的确定型TM。
核心思想：t步的格局变化问题——可产生性问题。
4、PSPACE类：在确定型图灵机在多项式时间内可以判定的语言类。P183。
5、P<=NP<=PSPACE<=NPSPACE<=EXPTIME。
6、PSPACE完全性：
B属于PSPACE，PSPACE中的每一个语言A可多项式时间可规约到B。
如果只有第二条满足，则称B为PSPACE难的。
7、PSPACE完全性问题：
补充：
前述范式：量词出现在语句的开头。带量词的布尔公式称为量词化布尔公式。全量词化布尔公式称为句子。全量词化：变量出现在某个量词的辖域内。
发表回复