《计算理论导引》PPT课件.ppt
,计算理论导引与算法复杂性Introduction to the Theory of Computation and Algorithm Complexities,主讲：刘国华（学院楼225室，）助教：辛婷婷（学院楼153室，）,6 BOOLEAN LOGIC1)Negation 0=1,1=02)Conjunction 01=0,11=13)Disjunction 01=14)Exclusive or 00=0,01=15)Equality 00=1,1 0=06)Implication 10=0,11=1,01=1,00=17)Distributive law P(QR)=(PQ)(PR)P(QR)=(PQ)(P R),CHAPTER 1 FUNDATION,Im sorry!,CHAPTER 2COMPUTATIONAL MODELS(1),Computation?,Computation is a general term for any type of process,algorithm or measurement;this often includes but is not limited to digital data.Computation is a process following a well-defined model.Computation is also a major subject matter of computer science:it investigates what can or cannot be done in a computational manner.,CHAPTER 2COMPUTATIONAL MODELS(1),AUTOMATATURING MACHINES,CHAPTER 2 COMPUTATIONAL MODELS(1),AUTOMATA1 FINITE AUTOMATA1)DETERMINISTIC FINITE AUTOMATA(DFA)Example.An automatic door.,Rules for opening:1 The door is closing,if some one is standing on the front pad(FRONT)and no one is standing on the rear pad(REAR),then the door opens;2 The door is opening,if some one is standing on the rear pad(REAR),then the door keeps opening;3 The door is opening,if some one is standing on the front pad and some one is standing on the rear pad(BOTH),then the door keeps opening;,CHAPTER 2 COMPUTATIONAL MODELS(1),Rules for closing:1 The door is opening,if no one is standing on either pad(NEITHER),then the door closes;2 The door is closing,if some one is standing on the rear pad(REAR),then the door keeps closing;3 The door is closing,if some one is standing on the front pad and some one is standing on the rear pad(BOTH),then the door keeps closing.,How to implement this system?,Hardwares:two sensors;one computer(only 1 bit memory),etc.,How about the software?,CHAPTER 2 COMPUTATIONAL MODELS(1),satrt,tTRUE;d 0,t=TRUE?,Y,s1sensor1,s2sensor2,d=0and(s2=1ors1=1ands2=1ors1=0ands2=0),Y,d=1and(s1=1ors2=1ors1=1ands2=1),N,Y,d=0ands1=1,N,Y,d1,d=1ands1=0ands2=0,Y,d0,N,end,N,N,CHAPTER 2 COMPUTATIONAL MODELS(1),CLOSED(d=0),OPEN(d=1),NEITHER(s1=0ands2=0),FORNT(s1=1),REAR(s2=1)BOTH(s1=1ands2=1)NEITHER(s1=0ands2=0),FORNT(s1=1)REAR(s2=1)BOTH(s1=1ands2=1),CHAPTER 2 COMPUTATIONAL MODELS(1),CLOSED,OPEN,NEITHER,FORNT,REARBOTHNEITHER,FORNTREARBOTH,CHAPTER 2 COMPUTATIONAL MODELS(1),front pad,rear pad,CLOSED,OPEN,BOTH,NEITHER,FORNT,BOTH,REAR,CHAPTER 2 COMPUTATIONAL MODELS(1),CLOSED,OPEN,NEITHER,FORNTREARBOTH,NEITHER,FORNTREARBOTH,CHAPTER 2 COMPUTATIONAL MODELS(1),The state diagram for DFA M1,1,11,01,001,00001,01,011,0011,00110,FORMAL DEFINITION OF A FINITE ATUOMATONA finite automaton is a 5-tuple(Q,q0,F),where1.Q is a finite set called the states,2.is a finite set called the alphabet,3.:Q Q is the transition function,4.q0Q is the start state,and5.F Q is the set of accept states.,CHAPTER 2 COMPUTATIONAL MODELS(1),The state diagram for DFA M1,1.Q=q1,q2,q3,2.=0,1,3.is desribed as 0 1 q1 q1 q2 q2 q3 q2 q3 q2 q24.q1 is the start state,and5.F=q2.,CHAPTER 2 COMPUTATIONAL MODELS(1),L(M)=A:Language of machine M,we say that M recoginizes A.FORMAL DEFINITION OF COMPUTATIONLet M=(Q,q0,F)be a finite automaton and let w=w1w2wn be a string where each wi is a member of the alphabet.Then M accepts w if a sequence of states r0,r1,rn in Q exists with three conditions:1.r0=q0,2.(r0,wi+1)=ri+1,for i=0,n-1,and3.rnF.Regular language:a language is called a regular language if some finite automaton recognizes,CHAPTER 2 COMPUTATIONAL MODELS(1),DESIGNING FINITE AUTOMATA,qeven,qodd,0,0,1,1,How to design a DFA to recognize the language of all strings that contain the string 001 as a substring.,q1,1,q2,q3,0,1,0,1,0,q4,1,0,CHAPTER 2 COMPUTATIONAL MODELS(1),THE REGULAR OPERATIONUnion:AB=x|xA or xBConcatenation:AB=xy|xA and yBStar:A=x1x2xk|k0 and each xiAEXAMPLE.A=good,bad,B=boy,girlAB=？AB=？A=?,*,*,AB=good,bad,boy,girlAB=goodboy,goodgirl,badboy,badgirlA=,good,bad,goodgood,goodbad,badbad,badgood,goodgoodgood,goodgoodbad,goodbadgood,goodbadbad,*,CHAPTER 2 COMPUTATIONAL MODELS(1),THEOREM 2.1 The class of regular languages is closed under the union operation.PROOF IDEA.A1=L(M1);A2=L(M2)A1A2=L(M3)?Let M1=(Q1,1,q1,F1),M2=(Q2,2,q2,F2),thenM3=(Q3,3,q3,F3),where Q3=(r1,r2)|r1Q1 and r2Q2,3(r1,r2),a)=(1(r1,a),2(r2,a),q3=(q1,q2),F=(r1,r2)|r1 F1 or r2F2,CHAPTER 2 COMPUTATIONAL MODELS(1),THEOREM 2.2 The class of regular languages is closed under the concatenation operation.,CHAPTER 2 COMPUTATIONAL MODELS(1),练习题：1 写出该状态图所表示DFA的形式化定义.,2 给定一个语言A=w|w以1结束，设计一个识别它的DFA.,
