**Finite Automata andNon Determinism**http://cis.k.hosei.ac.jp/~yukita/**State Diagram for M1**1 0 0 q3 q1 q2 1 0, 1**Task 01DFA**• Implement M1 with your favorite programming language. • GUI • Two buttons for input 0 and 1 • State chart with the current state highlighted**State Diagram for M5**0 q1 1 0, <RESET> 2, <RESET> 0 1 2 q0 q2 2 1, <RESET>**Informal Description of M5**• M5 keeps a running count of the sum of the numerical symbols it reads, modulo 3. • Every time it receives the <RESET> symbol it resets the count to 0. • M5 accepts if the sum is 0, modulo 3.**Definition 1.7: Regular Language**• A language is called a regular language if some finite automaton recognizes it.**Example 1.9: A finite automaton E2**• E2 recognizes the regular language of all strings that contain the string 001 as a substring. • 0010, 1001, 001, and 1111110011110 are all accepted, • but 11 and 0000 are not.**Find a set of states of E2**You • haven’t just seen any symbols of the pattern, • have just seen a 0, • have just seen 00 or, • have just seen the entire pattern 001. Assign the states q,q0,q00, and q001 to these possibilities.**Draw a State Diagram for E2**0, 1 1 0 q 0 q0 q00 q001 1 0 1**Proof of Theorem 1.12**Proof of Th 1.12**Construction of M**Proof of Th 1.12**Correctness**You should check the following. • For any string recognized by M1 is recognized by M. • For any string recognized by M2 is recognized by M. • For any string recognized by M is recognized by M1 or M2. Proof of Th 1.12**Nondeterminism**• To prove Theorem 1.13, we need nondeterminism. • Nondeterminism is a generalization of determinism. So, every deterministic automaton is automatically a nondeterministic automaton.**Nondetermistic Finite Automata**• A nondeterministic finite automaton can be different from a deterministic one in that • for any input symbol, nondeterministic one can transit to more than one states. • epsilon transition • NFA and DFA stand for nondeterministic finite automaton and deterministic finite automaton, respectively.**NFA N1**0,1 0,1 q3 1 q4 q1 q2 1 0,e**Parallel world and NFA**... ... accept**Example 1.14 NFA N2**0,1 q3 q4 q1 q2 0,1 1 0,1 Let language A consist of all strings over {0,1} containing a 1 in the third position from the end. N2 recognizes A.**A DFA equivalent to N2**0 0 q010 q110 q000 q100 0 0 1 0 1 1 0 0 1 0 1 q011 q111 q001 q101 1 1 1**Example 1.15 NFA N3**0 0 e 0 e 0 0 Let language A consist of all strings 0k , where k is a multiple of 2 or 3. N3 recognizes A.**A DFA equivalent to N3**0, 1 q-1 1 1 1 1 1 1 q4 q5 q0 q１ q２ q3 0 0 0 0 0 0**Example 1.16 NFA N4**q1 a b e a q3 q2 a,b N4 accepts e, a, baba, and baa. N4 does not accept b, nor babba.**0,1**0,1 1 0,e 1 q3 q4 q1 q2 Example 1.18 NFA N1**In what situation is Non Determinism relevant?**• Von Neumann machines are deterministic. • However, there are many cases where machine specification is all we need.**Theorem 1.19**• Every nondeterministic finite automaton has an equivalent deterministic finite automaton. • Def. The two machines are equivalent is they recognize the same language.**Proof of Th. 1.19**Proof of Th 1.19**Incorporate e arrows**Proof of Th 1.19**Corollary 1.20**• A language is regular if and only if some nondeterministic finite automaton recognizes it.**Example 1.21 NFA N4 to DFA**1 b a e a 3 2 a,b**Task 02Parallel World**• Write a program that simulates N4. • GUI • Three buttons for input 0, 1, and epsion. • State chart that reflect the branching of the world.**The state diagram of D**a,b a b {2} {1,2} f {1} a,b b b a b a a {2,3} {1,2,3} {3} a {1,3} a b b**Theorem 1.22The class of regular languages is closed under**the union operation. N N1 e e N2**N2**N1 Theorem 1.23The class of regular languages is closed under the concatenation operation. N e e**N1**Theorem 1.24The class of regular languages is closed under the star operation. N e e e