#### 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).

Transition table for NDFA from above NDFA transition diagram

State |
Input 0 |
Input 1 |

->q0 |
q0 |
q0, q1 |

q1 |
– |
*q2 |

q2 |
– |
– |

Transition table for DFA from above NDFA transition table

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.