Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

# RGPV notes Write short note on NDFA

#### RGPV 2002Q. 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}.