Session-5 .pptx

TOC Session 5 finite state systems- non deterministic finite automation- NDFA

1. Session 5: Finite State systems – Non Deterministic Finite Automaton – NDFA By Dr. Ashok Kumar

2. Formal Definition of NFAs Set of states, i.e. Input alphabet , i.e. Transition function Initial state Final states

3. 3 Alphabet = Nondeterministic Finite Accepter (NFA)

4. 4 Two choices Alphabet = Nondeterministic Finite Accepter (NFA)

5. 5 No transition Two choices No transition Alphabet = Nondeterministic Finite Accepter (NFA)

6. 6 First Choice

7. 7 First Choice

8. 8 First Choice

9. 9 “accept” First Choice All input is consumed

10. 10 Second Choice

11. 11 Second Choice

12. Second Choice No transition: the automaton hangs

13. 13 Second Choice “reject” Input cannot be consumed

14. 14 An NFA accepts a string: when there is a computation of the NFA that accepts the string all the input is consumed and the automaton is in a final state AND

15. 15 Example is accepted by the NFA: “accept” “reject” because this computation accepts

16. 16 Rejection example

17. 17 First Choice

18. 18 First Choice “reject”

19. 19 Second Choice

20. 20 Second Choice

21. 21 Second Choice “reject”

22. 22 An NFA rejects a string: when there is no computation of the NFA that accepts the string: All the input is consumed and the automaton is in a non final state The input cannot be consumed OR

23. 23 Example is rejected by the NFA: “reject” “reject” All possible computations lead to rejection

24. 24 Language accepted:

25. Language accepted:

26. Language accepted (redundant state)

27. Formal Definition The language accepted by NFA        is: where and there is some    (final state)

28. Remarks: The symbol never appears on the input tape Simple automata:

29. NFA DFA NFAs are interesting because we can express languages easier than DFAs