FOR FREE CONTENT

Difference between DFA and NFA:

 

Now we want to calculate the minimum number of states in Finite Automata

We want to a create automata for language L1 = {ab, ba}, Σ = {a, b} 

 

The above machine is not DFA because for every state all moves are not defined. So, the machine is NFA which has 4 states.

 

Now we create a DFA by adding a trap state.

So,

Minimum number of state in DFA = 5

Minimum number of state in NFA = 4

Minimum number of state in FA = Minimum number of state in NFA = 4

 

Generally, a minimum number of states in NFA is less than the minimum number of states in DFA.

 

Note: So, follow the question carefully, it asking you the minimum number of states in DFA or the minimum number of states in finite automata. 

 

Example: 

Find the minimum number of states in finite automata of the following language L = {00, 01, 010}.

 

Answer: 

 

So, the minimum number of states in finite automata: 04

 

Now we can derive a second NFA

Two NFA machines are different but the states the number of states are same.

Note: Minimal finite automata can be more than one (1). But the minimal state in automata can be unique.