RGPV TOC Short note on equivalent of DFA and NFA

RGPV 2010, 02
Q. 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


Reference:

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