资源描述：
《计算理论定理定义总结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、定义1.1：有穷自动机是一个5元组(Q,S,d,q0,F)，其中(1)Q是一个有穷集合，称为状态集。(2)S是一个有穷集合，称为字母表。(3)d:Q®S´Q是转移函数。(4)q0ÎQ是起始状态。(5)FÍQ是接受状态集。定义1.7：如果一个语言被一台有穷自动机识别，则称它是正则语言。DFA和NFA的区别：1、DFA每个状态对于字母表中的每个符号总是恰好有一个转移箭头射出。NFA一个状态对于字母表中的每一个符号可能有0个1个或多个射出的箭头；2、在DFA中，转移箭头上的标号是取自字母表的符号。而NFA
2、的箭头可以标记字母表中的符号或e。定义1.17：非确定型有穷自动机(NFA)是一个5元组(Q,S,d,q0,F)，其中(1)Q是有穷的状态集。(2)S是有穷的字母表。(3)d:Q´Sε®P(Q)是转移函数。(4)q0ÎQ是起始状态。(5)FÍQ是接受状态集。正则表达式的形式化定义：称R是一个正则表达式，如果R是(1)a，这里a是字母表S中的一个元素；(2)e；(3)Æ(4)R1∪R2，这里R1和R2是正则表达式；(5)R1°R2，这里R1和R2是正则表达式；(6)R1*，这里R1是正则表达式；定义1
3、.33：GNFAM=(Q,S,d,qstart,qaccept)（1）Q是有穷的状态集。(2)S是输入字母表。(3)d:(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)
4、y
5、>0；(3)
6、xy
7、≤p
8、上下文无关文法：(1)写下起始变元——第一条规则左边的变元。(2)取一个已写下的变元，并找到以该变元开始的规则，把这个变元替换成规则右边的字符串。(3)重复步骤2，直到写下的字符串没有变元。定义2.1：上下文无关文法是一个4元组(V,S,R,S)，且(1)V是一个有穷集合，称为变元集；(2)S是一个与V不相交的有穷集合，称为终结符集；(3)R是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成；(4)SÎV是起始变元。如果u=v，或者存在u1,u2,…,uk,k³0使得uÞu1Þ
9、u2Þ…ÞukÞv，则称u派生v，记作uÞ*v。最左派生：对于文法G中的一个字符串w的派生，如果在每一步都是替换左边剩下的变元，则称这个派生是最左派生。定义2.4：如果字符串w在上下文无关文法G中有两个或两个以上不同的最左派生，则称G歧义地(ambiguously)产生字符串w，如果文法G歧义地产生某个字符串，则称G是歧义的。某些上下文无关语言只能用歧义文法产生，这样的语言是固有二义的。定义2.5：称一个上下文无关文法是为乔姆斯基范式(Chomskynormalform)，如果它的每一个规则具有如下
10、形式：A®BCA®a其中a是任意的终结符，A、B和C是任意的变元，且B和C不能同时是起始变元。此外，允许规则S®e，其中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——FÍQ，终止状态集合。定理2.12：一个语言是上下
11、文无关的，当且仅当存在一台下推自动机识别它。引理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∈
12、A；2.
13、vy
14、>0；3.
15、vxy
16、£p。定义3.1：TM是一个7元组(Q,S,G,d,q0,qAcc,qRej)，其中：（1）Q：状态集（2）S：输入字母表,不包括空白字符（3）G：带字母表, ÎGandSÌG（4）d：转移函数d:QxGàQxGx{L,R},（5）q0：开始状态（6）qAcc：接受状态,（7）qRej：拒绝状态。格局：当前状态qÎQ当前带内容ÎG*读写头位置Î{0,1,2,…}定义3.2：如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。定
