1.3.2 non deterministic finite automaton

What is NDFA?
Definition of NDFA.
Different representation of NDFA.
some problems in NDFA

1. Non-deterministic Finite Automaton (NDFA/NFA) Sampath Kumar S, AP/CSE, SECE

2. Non - Deterministic Finite Automaton (NDFA/NFA) In NDFA, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the machine moves cannot be determined. Hence, it is called  Non-deterministic Automaton.   As it has finite number of states, the machine is called  Non-deterministic Finite Machine  or  Non-deterministic Finite Automaton . 7/14/2016 2 Sampath Kumar S, AP/CSE, SECE

3. Formal definition of NFA: A NFA can be represented by a 5-tuples (Q, ∑, δ, q , F ) where − Q   is a finite set of states. ∑  is a finite set of symbols, called the  alphabet  of the automaton. δ   is the transition function where δ: Q × {∑ ∪ ε} → 2Q (Here the power set of Q (2 Q ) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states) q  is the initial state from where any input is processed (q  ∈ Q). F  is a set of final state/states of Q (F ⊆ Q). Note : δ is called Delta and ∑ is called Sigma 7/14/2016 3 Sampath Kumar S, AP/CSE, SECE

4. Graphical Representation of a NFA A DFA is represented by digraphs called  state diagram or Transition Diagram . The vertices represent the states . The arcs labeled with an input alphabet show the transitions . The initial state is denoted by an empty single incoming arc . The final state is indicated by double circles . 7/14/2016 4 Sampath Kumar S, AP/CSE, SECE

5. Example Let a non-deterministic finite automaton be → Q = {a, b, c} ∑ = {0, 1} q  = {a} F={c} The transition function δ as shown below − 7/14/2016 5 Sampath Kumar S, AP/CSE, SECE Present State Next State for Input 0 Next State for Input 1 ->a a,b b b c a,c c* b,c c

6. Example Cont.., Its graphical representation would be as follows: Can you guess the language of above NFA? 7/14/2016 6 Sampath Kumar S, AP/CSE, SECE

7. DFA vs NDFA DFA NFA The transition from a state is to a single particular next state for each input symbol. Hence it is called  deterministic . The transition from a state can be to multiple next states for each input symbol. Hence it is called  non-deterministic . Empty string transitions are not seen in DFA. NDFA permits empty string transitions. Backtracking is allowed in DFA In NDFA, backtracking is not always possible. Requires more space. Requires less space. A string is accepted by a DFA, if it transits to a final state. A string is accepted by a NDFA, if at least one of all possible transitions ends in a final state. 7/14/2016 7 Sampath Kumar S, AP/CSE, SECE

8. Problems to Discuses: Design NFA for the language L={w|all the string w ends with 00 , where ∑={0,1} } Design NFA for the language L={w|all the string w begins with 00 , where ∑={0,1} } String starts with a zero followed by any number of 1’s or zeros followed by any number of 0’s String such that every 1 is followed immediately by 00. Design a NFA which consists of 101 as the substring. 7/14/2016 8 Sampath Kumar S, AP/CSE, SECE

9. Problems (Cont..,): Construct a NFA for a language L which accepts all the strings in which the 3 rd symbol from right end is always a over ∑={a, b}. Design NFA accepting all strings ending with 01 over ∑={0,1}. Design NFA accepting all strings ending with aa over ∑={ a,b }. Construct NFA accepting binary strings with 2 consecutive 0’s. 7/14/2016 9 Sampath Kumar S, AP/CSE, SECE

10. 7/14/2016 Sampath Kumar S, AP/CSE, SECE 10

11. நன்றி  7/14/2016 Sampath Kumar S, AP/CSE, SECE 11