资源描述：
《计算理论总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、有限状态机1给出一有限状态机，回答其起始状态，接受状态，接受的字符串，等等。假设字母表是｛0,1｝,构造能够识别包含字符串001的所有字符串自动机DFAo（例7）设工二｛0｝，设计识别（/,其中k是2或3的倍数的NFAo（例10）根据正则语言的封闭性，由简单的有限状态机构造复杂的有限状态机。（难点）2DFA,NFA与正则表达式的等价关系（证明），以及它们的相互转换（必考）。求与下图左图NFA等价的DFA（例11）o求下面右图DFA对应的正则表达式（例14）P46b证明B=｛0nln
2、n^0）不是正则语言。同理，证明回文的
3、非正则性。证：假设3是正则的，而卩是其相应的泵长度。考虑字符串5=而s=xyz为在泵引理下的分段，贝■若g=0^,00,则xyyz年B4“两个正则语言等价”判断二、上下文无关文法1由表达式写上下文文法（必考）；或判断某一字符串W能否由某一上下文文法产生。构造得JlJ{Onln
4、n>O}U{ln
5、Onn^O）的文法。（例4、例5、例］）■{Onln
6、n>0}文法的构造:Si->OSil
7、£■{ln0n
8、n>0}文法的构造：S2TIS2O
9、£■S
10、—Si
11、S?2语法分析树。乔姆斯基范式。3构造PDAo（必考）构造识别{卩涉»丘{0,1}*}的PDA。（例8、例9、例10）4泵引理。证明anbncn不是上下文无关。（例14）设泵长度为p,考虑字符串s=uvxyz9其中。或9不是空串。考虑字符串uv2xy2z:■若°妙都只包含一种符号，则uv2xy2z中a,个数不可能相同，即其不属于E；■若Q或y中含有2个符号，贝^uv2xy2z中a,b,c的次序不对，即其不属于〃；三、图灵机首先要搞清楚儿个定义：图灵机、图灵可识别、判定器、图灵可判定。掌握如何描述一个图灵机（TM）,看
12、懂PPT上例1和例3即可。例1（构造语言为L={Onln
13、n>=l）的TM）基本思路：从最左侧开始，进入以下循环循环将0改成X,然后向右移动直到到达1；将1改成Y,然后向左移动直到发现某个X；对于X右侧的0重复以上操作；_(qO,0)=(ql,X,R)将0改成X_(ql,0)=(ql,0,R)向右找1_(ql,Y)=(ql,Y,R)向右找1_(ql,1)二(q2,Y,L)将1改成Y,返回_(q2,Y)=(q2,Y,L)_(q2,X)=(qO,X,R)遇X右移,进入状态q0及(1)循环_(q2,0)=(q2,0,L)向左找X后
14、面的0_(q0,Y)=(q3,Y,R)0己全改X后遇到Y,进入q3_(q3,Y)=(q3,Y,R)向右找_(q3,)二(q4,,0)0,1个数相当，接受并停机拒绝：_(q3,1)=(qreject,1,0)1的个数比0的个数多，拒绝_(q3,0)=(qreject,0,0)1后面还有0,拒绝_(ql,)=(qreject,,0)0的个数比1的个数多,拒绝考虑初始格局qOOOll：qOOOll'XqlOll'XOqlll'Xq20Y1'q2X0Y1'XqOOY1'XXqlY1'XXYqll'XXq2YY'Xq2XYY'XXqO
15、YY'XXYq3Y'XXYYq3'XXYYq4考虑初始格局qOOOlO:qOOOlO'XqlOlO'XOqllO'Xq20Y0'q2X0Y0'XqOOY0'XXqlY0'XXYqlO'XXYOql例3(判定A={02n
16、n>=0}的TM)基本思路：从最左侧开始，进入以下循环循环将0改成X,然后向右移动直到到达1；将1改成Y,然后向左移动直到发现某个X；对于X右侧的0重复以上操作；四、可判定性语言/规约首先：Adfa,Anfa,Arex,Edfa,EQdfa,A（：fg,R:fg这些都是可判定语言。这个虽然不考，但应该知道。其
17、次：Atm,Etm,HALTtm.EQtm是不可判定的，其证明过程要掌握。定理7（ATM是可识别不可判定的）可识别的证明。设置通用图灵机U,对于输入＜M,w＞执行：1对于输入w,模拟M;2若M进入接受状态，则接受；如果进入拒绝状态，则拒绝。不可判定性的证明。假设ATM是可判定的，H为其判定其。即对于输入〈M,w＞若M接受w,则H接受＜M,w＞；若M不接受w,则H拒绝＜M,w＞；即/、（接受若皿接受力［拒绝若M不接受3图灵机D的构造：对于输入的图灵机M的描述＜M＞,执行若M接受vM＞,则拒绝若M不接受＜M＞,则接受；即接受拒绝
18、若H（〈M,〈M〉〉）=拒绝若〈M〉〉）=接受考虑D():D(〈G)=接受若。不接受〈。〉拒绝若D接受（D）定理10（HALTtm是不可判定的）证明：假设TMR判定HALT™,则构造TMS如e：对于输入＜M,w＞,S执行对于输入〈M,v＞执行TMR；如果R拒绝，则拒绝；否则在w上模
