Some important uses of DFA and NFA

Example 1:

let us say we have to make a Finite Automata such that second character from left is  a

This can be done using DFA

and  Σ={a,b}

then L={ba,aa,aab,bab ....etc}

So no of states here is: n+ 2

Example 2: Finite Automata such that second character from right is a.

Solution: To do this we need NFA, it can be done using DFA but it takes a lot of time.

 

 

 what we have done is :

first, we made NFA then we convert that NFA into DFA, in DFA we have four states.

 

 

Contributor's Info

Created:
0Comment
Diffrence between DFA and NFA

DFA:

  1. DFA” stands for “Deterministic Finite Automata.
  2. In DFA the next possible state is distinctly set.
  3. DFA cannot use empty string transition.
  4. Backtracking is allowed in DFA.
  5. DFA requires more space.

NFA:

  1. NFA” stands for “Nondeterministic Finite Automata.”
  2. In NFA each pair of state and input symbol can have many possible next states.
  3. NFA can use empty string transition.
  4.  NFA requires less space.
  5. Backtracking may or may not be allowed in NFA.

but in term of power, DFA is equivalent to NFA.

If there are n states in NFA then equivalent DFA may have at most 2n states.

Contributor's Info

Created:
0Comment
Difference between DFA and NFA

                                NFA

                          DFA

In Deterministic Finite Automata, exactly one state transition for every input symbol.

In NFA, for the same input symbol, there can be more than one next state symbol. Also, there can be epsilon transitions.

Conversion of Regular expression to DFA is complex.

A regular expression can be easily converted to NFA using Thomson’s construction.

DFA requires more memory for storing information.

NFA requires move computations to match Regular Expressions with input.

It is impossible to move next state without reading any symbol.

In NFA, we can move to the next state without reading any symbol.

EXAMPLE:

Construct a DFA that accepts all starting with “a”.

Q={A,B,D(dead state)}

∑ = {a,b}

L ={aa, ab, abb….aaab}

 

 

 

 

 

EXAMPLE:

Construct a NFA that accepts all starting with “a”.

Q={A,B}

∑ = {a,b}

L ={aa, ab, abb….aaab}

There is a concept of Dead state when a machine enters the dead state, there is no way to reach the final state. A machine may have several dead states but at most only one dead state is needed by a machine(DFA).

There is no concept of dead state.

No. of states : DFA ≥  NFA No. of states : DFA≥​ NFA

 

 

Contributor's Info

Created:
0Comment