《情报科学部-FiniteAutomataandNonDeterminism.ppt》由会员分享，可在线阅读，更多相关《情报科学部-FiniteAutomataandNonDeterminism.ppt（46页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。
1、情报科学部-FiniteAutomataandNonDeterminism Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望Definition 1.1:Finite Automaton2State Diagram for M1q3q1q201100,13Data Representation for M14Task 01DFA1.Implement M1 with your favorite programming language.2.GUITwo button
2、s for input 0 and 1State chart with the current state highlighted5Language of M16State Diagram for M5q2q1q001122,1,20,07Data Representation for M58Informal Description of M5M5 keeps a running count of the sum of the numerical symbols it reads,modulo 3.Every time it receives the symbol it resets the
3、count to 0.M5 accepts if the sum is 0,modulo 3.9Definition 1.7:Regular LanguageA language is called a regular language if some finite automaton recognizes it.10Example 1.9:A finite automaton E2E2 recognizes the regular language of all strings that contain the string 001 as a substring.0010,1001,001,
4、and 1111110011110 are all accepted,but 11 and 0000 are not.11Find a set of states of E2You1.havent just seen any symbols of the pattern,2.have just seen a 0,3.have just seen 00 or,4.have just seen the entire pattern 001.Assign the states q,q0,q00,and q001 to these possibilities.12 Draw a State Diagr
5、am for E2q00q00100,1110q00q113Regular Operations on Languages14Example 1.1115Theorem 1.12 Closedness for Union16Proof of Theorem 1.1217Proof of Th 1.12Construction of M18Proof of Th 1.12CorrectnessYou should check the following.1.For any string recognized by M1 is recognized by M.2.For any string re
6、cognized by M2 is recognized by M.3.For any string recognized by M is recognized by M1 or M2.19Proof of Th 1.12Theorem 1.13 Closedness for concatenation20NondeterminismTo prove Theorem 1.13,we need nondeterminism.Nondeterminism is a generalization of determinism.So,every deterministic automaton is a
7、utomatically a nondeterministic automaton.21Nondetermistic Finite AutomataA nondeterministic finite automaton can be different from a deterministic one in thatfor any input symbol,nondeterministic one can transit to more than one states.epsilon transitionNFA and DFA stand for nondeterministic finite
8、 automaton and deterministic finite automaton,respectively.22NFA N1q3q1q20,110,eq40,1123Parallel world and NFA.accept24Example 1.14 NFA N2q3q1q20,110,1q40,1Let language A consist of all strings over 0,1 containing a 1 in the third position from the end.N2 recognizes A.25A DFA equivalent to N2q010q00
9、0q100000q110q011q001q1011q11110100101101126Example 1.15 NFA N3e0Let language A consist of all strings 0k,where k is a multiple of 2 or 3.N3 recognizes A.e000027A DFA equivalent to N30qqq3q50q0000q40q-11111110,128Example 1.16 NFA N4q1q2q3aba,beaN4 accepts e e,a,baba,and baa.N4 does not accept b,nor b
10、abba.29Definition 1.17:NFA30Example 1.18 NFA N1q3q1q20,110,eq40,1131In what situation is Non Determinism relevant?Von Neumann machines are deterministic.However,there are many cases where machine specification is all we need.32Theorem 1.19Every nondeterministic finite automaton has an equivalent det
11、erministic finite automaton.Def.The two machines are equivalent is they recognize the same language.33Proof of Th.1.1934Proof of Th 1.19Incorporate e arrows35Proof of Th 1.19Corollary 1.20A language is regular if and only if some nondeterministic finite automaton recognizes it.36Example 1.21 NFA N4
12、to DFA123aba,bea37Task 02Parallel World1.Write a program that simulates N4.2.GUIThree buttons for input 0,1,and epsion.State chart that reflect the branching of the world.38Start and Accept states39The state diagram of Df121,231,32,31,2,3a,ba,baaaaaabbbbbb40Theorem 1.22 The class of regular languages is closed under the union operation.N1N2Nee41Proof of Th.1.2242Theorem 1.23 The class of regular languages is closed under the concatenation operation.N1N2Nee43Proof of Th.1.2344Theorem 1.24 The class of regular languages is closed under the star operation.N1Neee45Proof of Th.1.2446
黑公网安备:91230400333293403D