Q47,Paper3, D12. The minimum number of states of the non-deterministic finite automation which accepts the language {a b a b^n|n >=0} union {a b a^n|n >=0} is

(A) 3

(B) 4

(C) 5

(D)6.

Answer©

Explanation.

There is no polynomial time algo to find minimum number of states.

L1={aba} when n=0.

{abab} when n=1.

{ababb} when n=2.

 L2={ab} when n=0

{aba} when n=1

{abaa} when n=2

{abaaa} when n=3.

L1union L2={ab,aba,abab,abaa,ababb,abaaa-----}.

ab(a+b)*

Hence 5 states.