RGPV notes Write short note on NDFA

RGPV 2002
Q. Write a short note on non-deterministic finite automta ?

Ans. Non deterministic finite automata refere as NDFA or NFA allows a set of possible moves. 
For example from a state an input ‘1’ can transit 0 times, 1 times or more than 1 times.
Its not determined in NFA like in DFA.
NDFA is defined as 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.
To understood NDFA, lets compare it with DFA.

NDFA

DFA

Non Deterministic Finite Automata

Deterministic Finite Automata

Empty String transition allowed in DDFA.

Empty String transition not allowed in DFA.

In NDDFA, the next possible state is not determined.

In DFA, the next possible state is determined.

For NDFA, DFA may or may not exist.

For all DFA there exist NDFA

NDFA is like combination of many machines.

DFA is like a single machine.

NDFA is easy to construct.

DFA is touch to construct compare to NDFA.

Some examples of NDFA:
Problem 01: Construct a NDFA for the language accepting strings having even number of 1’s over input alphabets ∑ = {0, 1}.

Problem 02: Construct a NDFA for the language accepting strings containg ’01’ as substring over input alphabets ∑ = {0, 1}.


Problem 03: Construct a NDFA for the language accepting strings containg ‘0’ as divisible by 3 over input alphabets ∑ = {0, 1}.