Limited Automata and Non Determinism - PowerPoint PPT Presentation

finite automata and non determinism l.
Skip this Video
Loading SlideShow in 5 Seconds..
Limited Automata and Non Determinism PowerPoint Presentation
Limited Automata and Non Determinism

play fullscreen
1 / 46
Download
Download Presentation

Limited Automata and Non Determinism

Presentation Transcript

  1. Finite Automata andNon Determinism http://cis.k.hosei.ac.jp/~yukita/

  2. Definition 1.1: Finite Automaton

  3. State Diagram for M1 1 0 0 q3 q1 q2 1 0, 1

  4. Data Representation for M1

  5. Task 01DFA • Implement M1 with your favorite programming language. • GUI • Two buttons for input 0 and 1 • State chart with the current state highlighted

  6. Language of M1

  7. State Diagram for M5 0 q1 1 0, <RESET> 2, <RESET> 0 1 2 q0 q2 2 1, <RESET>

  8. Data Representation for M5

  9. 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.

  10. Definition 1.7: Regular Language • A language is called a regular language if some finite automaton recognizes it.

  11. 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.

  12. 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.

  13. Draw a State Diagram for E2 0, 1 1 0 q 0 q0 q00 q001 1 0 1

  14. Regular Operations on Languages

  15. Example 1.11

  16. Theorem 1.12 Closedness for Union

  17. Proof of Theorem 1.12 Proof of Th 1.12

  18. Construction of M Proof of Th 1.12

  19. 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

  20. Theorem 1.13 Closedness for concatenation

  21. Nondeterminism • To prove Theorem 1.13, we need nondeterminism. • Nondeterminism is a generalization of determinism. So, every deterministic automaton is automatically a nondeterministic automaton.

  22. 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.

  23. NFA N1 0,1 0,1 q3 1 q4 q1 q2 1 0,e

  24. Parallel world and NFA ... ... accept

  25. 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.

  26. 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

  27. 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.

  28. A DFA equivalent to N3 0, 1 q-1 1 1 1 1 1 1 q4 q5 q0 q1 q2 q3 0 0 0 0 0 0

  29. 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.

  30. Definition 1.17: NFA

  31. 0,1 0,1 1 0,e 1 q3 q4 q1 q2 Example 1.18 NFA N1

  32. In what situation is Non Determinism relevant? • Von Neumann machines are deterministic. • However, there are many cases where machine specification is all we need.

  33. 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.

  34. Proof of Th. 1.19 Proof of Th 1.19

  35. Incorporate e arrows Proof of Th 1.19

  36. Corollary 1.20 • A language is regular if and only if some nondeterministic finite automaton recognizes it.

  37. Example 1.21 NFA N4 to DFA 1 b a e a 3 2 a,b

  38. 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.

  39. Start and Accept states

  40. 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

  41. Theorem 1.22The class of regular languages is closed under the union operation. N N1 e e N2

  42. Proof of Th. 1.22

  43. N2 N1 Theorem 1.23The class of regular languages is closed under the concatenation operation. N e e

  44. Proof of Th. 1.23

  45. N1 Theorem 1.24The class of regular languages is closed under the star operation. N e e e

  46. Proof of Th. 1.24