#### RGPV 2010, 02

Q. Write short note on equivalent of DFA and NDFA ?

Ans.

- Every DFA is an NDFA.
- If from a regular set an NDFA is created than there may be chances of existence of DFA.

DFA is 5 tuple machine:

M = (Q, Σ, δ, q0, F)

- Q is a finite non empty set of states.
- Σ is a finite non empty set of input symbols.
- δ is a transition function, QXΣ int to Q
- q0 is an initial state belong to Q.
- F is the set of final states belong to Q.

NDFA is 5 tuple machine:

M = ( Q, Σ, δ, q0, F )

- Q is a finite non empty set of states.
- Σ is a finite non empty set of input symbols.
- δ is a transition function, QXΣ int to 2
^{Q } - q0 is an initial state belong to Q.
- F is the set of final states belong to Q.

**Problem 01:**Convert the following Non-Deterministic Finite Automata (NDFA) to Deterministic Finite Automata (DFA).

State | Input 0 | Input 1 |

->q0 | q0 | q0, q1 |

q1 | – | *q2 |

q2 | – | – |

State | Input a | Input b |

->q0 | q0 | {q0, q1} |

{q0, q1} | q0 | *{q0, q1, q2} |

*{q0, q1, q2} | q0 | *{q0, q1, q2} |

Transition diagram from above DFA transition table

- Introduction to Automata Theory Language & Computation, Hopcroft& Ullman,
- Theory of Computation, Chandrasekhar & Mishra, PHI.