定义1.1：有穷自动机是一个 5 元组 ( Q, , , q0, F )，其中(1) Q 是一个有穷集合，称为状态集。(2) 是一个有穷集合，称为字母表。(3) : QQ是转移函数。(4) q0Q 是起始状态。(5) FQ 是接受状态集。
定义1.7：如果一个语言被一台有穷自动机识别，则称它是正则语言。
DFA和NFA的区别：1、DFA每个状态对于字母表中的每个符号总是恰好有一个转移箭头射出。NFA一个状态对于字母表中的每一个符号可能有0个1个或多个射出的箭头；2、在DFA中，转移箭头上的标号是取自字母表的符号。而NFA的箭头可以标记字母表中的符号或。
定义1.17：非确定型有穷自动机 (NFA) 是一个 5 元组 ( Q, , , q0, F )，其中(1) Q 是有穷的状态集。(2) 是有穷的字母表。(3) : QεP(Q)是转移函数。(4) q0Q 是起始状态。(5) FQ 是接受状态集。
正则表达式的形式化定义：称 R 是一个正则表达式，如果 R 是(1) a，这里 a 是字母表 中的一个元素；(2) ；(3)
(4) R1∪R2，这里 R1 和 R2 是正则表达式；(5) R1R2 ，这里 R1 和 R2 是正则表达式；(6) R
1* ，这里 R1 是正则表达式；
定义1.33：GNFA M = (Q, , , qstart, qaccept)（1）Q 是有穷的状态集。(2) 是输入字母表。(3) :(Q-{qaccept})(Q-{qstart}) R 是转移函数。 (4) qstart 是起始状态。(5) qaccept 是接受状态。其中 R 是正则表达式。
定理1.37（泵引理）：若 A 是一个正则语言，则存在一个数 p (泵长度) 使得，如果 s 是 A 中任一长度不小于 p 的字符串，那么 s 可以被分成 3 段，s = xyz，满足下述条件：(1) 对于每一个 i 0, xyiz∈A ；(2) | y | 0；(3) | xy | ≤ p
上下文无关文法：(1) 写下起始变元——第一条规则左边的变元。(2) 取一个已写下的变元，并到以该变元开始的规则，把这个变元替换成规则右边的字符串。(3) 重复步骤2，直到写下的字符串没有变元。
定义2.1：上下文无关文法是一个 4 元组 ( V, , R, S )，且(1) V 是一个有穷集合，称为变元集；(2) 是一个与 V 不相交的有穷集合，称为终结符集；(3) R 是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成；(4) SV 是起始变元。
如果 u = v ，或者存在 u1, u2, …, uk, k 0 使得u u1 u2… uk v，则称 u 派生 v，记作 u * v。
最左派生：对于文法 G 中的一个字符串 w 的派生，如果在每一步都是替换左边剩下的变元，则称这个派生是最左派生。
定义2.4：如果字符串 w 在上下文无关文法 G 中有两个或两个以上不同的最左派生，则称 G 歧义地(ambiguously) 产生字符串 w，如果文法 G 歧义地产生某个字符串，则称 G 是歧义的。某些上下文无关语言只能用歧义文法产生，这样的语言是固有二义的。
定义2.5：称一个上下文无关文法是为乔姆斯基范式(Chomsky normal form)，如果它的每一个规则具有如下形式：A BC A a其中 a 是任意的终结符，A、B 和 C 是任意的变元，且 B 和 C 不能同时是起始变元。此外，允许规则S ，其中 S 是起始变元。
定理2.6：任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。
定义2.8：PDA是一个6元组M=(Q,Σ,Γ,δ, q0, F)，其中(1)Q——状态的有限集合。(2)Σ——输入字母表。(3)Γ——栈字母表。(4)δ：状态转移函数，Q×Σε ×Γε P（ Q×Γε ） 。(5)q0——q0∈Q，开始状态。 (6)F——FQ，终止状态集合。
定理2.12：一个语言是上下文无关的，当且仅当存在一台下推自动机识别它。
引理2.13：如果一个语言是上下文无关的，则存在一台下推自动机识别它。
引理2.15：如果一个语言被一台下推自动机识别，则它是上下文无关的。
断言2.16：如果Apq产生x，则x能够把P从p和空栈一块带到q和空栈。
断言2.17：如果x能够把P从p和空栈带到q和空栈，则Apq产生x。
定理2.19：如果A是上下文无关语言，则存在数p（泵长度），使得A中任何一个长度不小于p的字符串s都能被划分为5段s = uvxyz且满足下述条件：1. 对于每一个i 0, uvixyiz ∈A；2. |vy| 0；3. |vxy| p。
定义3.1：TM是一个7元组(Q, , , , q0, qAcc, qRej) ，其中：（1）Q ： 状态集（2） ： 输入字母表, 不包括空白字符（3） ： 带字母表, and （4）  ： 转移函数 : Q x Q x x { L, R }, （5）q0：开始状态（6）qAcc： 接受状态,（7） qRej：拒绝状态。
格局：当前状态q Q  当前带内容 *  读写头位置 {0,1,2,…}
定义3.2：如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。
定义3.3：如果一个语言能被某一图灵机判定，则称它是图灵可判定的。
定理3.8：每个多带图灵机等价于某一个单带图灵机
推论3.9：一个语言是图灵可识别的，当且仅当存在多带图灵机识别它。
定理3.10：每个非确定型图灵机等价于某一个确定图灵机
推论3.11：一个语言是图灵可识别的，当且仅当存在非确定性图灵机识别它。
推论3.12：一个语言是可判定的，当且仅当存在非确定性图灵机判定它。
定理3.13：一个语言是图灵可识别的，当且仅当有枚举器枚举
图灵机描述：形式化描述：详尽地写出图灵机的状态、转移函数等，属于最低层次、最详细程度的描述；实现描述：使用日常语言描述图灵机动作，如怎么移动读写头、怎么在带上存储数据等，这种程度的描述没有给出状态和转移函数的细节；高水平描述：也使用日常语言来描述算法，但忽略了实现的模型，不需要提及机器怎样管理它的带子或读写头。
定理4.1：ADFA是一个可判定语言。
定理4.2：ANFA是一个可判定语言。
定理4.3：AREX 是一个可判定语言。
定理4.4：EDFA 是一个可判定语言。
定理4.5：EQDFA是一个可判定语言。
定理4.6：ACFG是一个可判定语言。
定理4.7：ECFG是一个可判定语言。
定理4.8：每个上下文无关语言都是可判定的。
定理4.9：ATM 是不可判定的。
定义4.10：设 A 和 B 是两个集合，f 是从 A 到 B 的函数。如果 f从不将 两个不同元素映射到同一个对象，即：只要a ≠b 就有 f (a)≠f (b)，则称 f 是一对一映射的。如果 f 能击中 B 的每
个元素，即：对 B 的每个元素b，都存在 a A，使得 f (a) =b，则称 f 是满映射。如果存在函数 f：A B，f 是一对一映射又是满映射，则称集合 A 和 B 有相同规模。而既是一对一映射又是满映射的函数称为对应。在对应中，A 的每个元素映射到 B 的唯一一个元素，且 B 的每个元素都有A的唯一一个元素映射到它。对应就是将 A 的元素与 B 的元素进行配对的方法。
定义4.12：如果一个集合 A 是有限的或者与 N 有相同的规模，则 A 是可数的。
推论4.15：存在不能被任何图灵可识别的语言。
定理4.16：一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。
可以证明：如果一个语言和它的补都是图灵可识别的，则此语言也是可判定的。
这样，对任何不可判定语言，它或它的补至少有一个不是图灵可识别的。
一个语言的补是由不在此语言中的所有串构成的语言。
如果一个语言是一个图灵可识别语言的补集，则称它是补图灵可识别的。
推论4.17：Ā TM 不是图灵可识别的。
定理5.1：HALTTM是不可判定的。
定理5.2：ETM 是不可判定的。
定理5.3：REGULARTM是不可判定的。
定理5.4：EQTM是不可判定的。
定义5.5：设M是一个图灵机，w是一个串。M在w上的一个接受计算历史是一个格局序列C1，C2，．．．,Cl，其中C1是M在w上的起始格局，Cl是M的一个接受格局，且每个Ci都是Ci-1的合法结果，即符合M的规则。M在w上的一拒绝计算历史可类似定义，只是Cl应是一个拒绝格局。
定义5.6：线性界限自动机是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就保持在原地不动。这与普通图灵机的读写头不会离开带子的左端点的方式一样。
引理5.7：设M是有q个状态和g个带符号的LBA。对于长度为 n的带子，M恰有qngn个不同的格局。
定理5.8：ALBA是可判定的。
定理5.9：ELBA是不可判定的
定理5.10：ALLCFG是不可判定的。
定义5.12：函数f： * * 是一个可计算函数，如果有图灵机M，使得在每个输入w上 停机，且此时只有f(w)出现在带上。
定义5.15：语言A是映射可归约到语言B的，如果存在可计算函数 f： **使得对每个w，w∈A等价于f(w) ∈B记作A≤mB。称函数f为A到B的归约。
定理5.16：如果A≤mB且B是可判定的，则A也是可判定的。
推论5.17：如果A≤mB且A是不可判定的，则B也是不可判定的。
定理5.22：如果A≤字符串长度算不算 0mB，且B是可图灵可识别的，则A也是图灵可识别的。
推论5.23：如果A≤mB，且A不是图灵可识别的，则B也不是图灵可识别的。
定理5.24：EQTM既不是图灵可识别的，也不是补图灵可识别的。
引理6.1：存在可计算函数 q: * * ，对任意串w, q(w)是图灵机Pw的描述，Pw打印出w，然后停机。
SELF的构造：（1）A部分首先运行，再根据完成情况将控制传给B。A的任务是打印出B的描述。B的任务是打印出A的描述。（2）先构造A部分（3）使用机器P<B>来定义A，其中P<B>用函数q在<B>处的值q(<B>)描述，这样，A部分是一个打印出<B>的图灵机。A的描述依赖于是否已经有了B的描述，所以在构造出B之前，无法完成A的描述。（4）对于B部分：从A产生的输出来计算A（5）如果B能够得到<B>，就能应用q来得到<A>。但B如何得到<B>？当A结束时，它被留在带上。所以B只要看着带子就能得到<B>。计算q(<B>)=<A>之后，B将之加到带的前面。然后将A和B组合成一个机器并在带上写下它的描述<AB>=<SELF>。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。