# Limited Automata and Non Determinism - PowerPoint PPT Presentation  Limited Automata and Non Determinism

## 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 q１ q２ 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