Non-Deterministic Finite Automata_Theory of Computation.pptx

Non-Deterministic Finite Automata

1. Non-Deterministic Finite Automata (NFA) Dr. Balamurugan M Associate Professor Acharya Institute of Graduate Studies Bangalore

2. Formal Definition A Non-deterministic Finite State Automaton (NFA) is a 5-tuple : M= (Q, Σ, δ, qo, F) where Q is a finite set of states. Σ is a finite input alphabet. δ is the transition function mapping from Q x Σ into 2Q which is the power set of Q, the set of all subsets of Q; for each state q and input symbol a. qo ∈ Q is the initial state. F ⊆ Q is the set of final states. It is assumed here that there may be more than one final state.

3. NFA In NFA the current state there could be multiple next states The next state may be chosen at random All the next states may be chosen in parallel

4. Steps to design a NFA 1. Understand the language for which the NFA has to be designed and write the language for the set of strings starting with minimum string that are accepted by FA. 2. Draw transition diagram for the minimum length string. 3. Obtain the possible transitions to be made for each state on each input symbol. 4. Draw the transition table. 5. Test NFA with few strings that are accepted and few strings that are rejected by the given language. 6. Represent NFA with tuples.

5. Examples

6. 4.Design an NFA to recognize the following set of strings abc, abd and aad

7. 5. Obtain an NFA to recognize the following set of strings 0101,101 and 011

8. Thank You