# RGPV TOC Short note on equivalent of DFA and NFA

#### RGPV 2010, 02Q. Write short note on equivalent of DFA and NDFA ?

Ans.
1. Every DFA is an NDFA.
2. 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)
1. Q is a finite non empty set of states.
2. Σ is a finite non empty set of input symbols.
3. δ is a transition function, QXΣ int to Q
4. q0 is an initial state belong to Q.
5. F is the set of final states belong to Q.
NDFA is 5 tuple machine:
M = ( Q, Σ, δ, q0, F )
1. Q is a finite non empty set of states.
2. Σ is a finite non empty set of input symbols.
3. δ is a transition function, QXΣ int to 2
4. q0 is an initial state belong to Q.
5. 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
1. Introduction to Automata Theory Language & Computation, Hopcroft& Ullman,
2. Theory of Computation, Chandrasekhar & Mishra, PHI.