The Gateway to Computer Science Excellence
+4 votes

The minimum number of states of the non-deterministic finite automaton which accepts the language

$\{ a b a b^n \mid n \geq 0 \} \cup \{ a b a^n \mid n \geq 0 \}$ is

  1. 3
  2. 4
  3. 5
  4. 6
in Theory of Computation by
recategorized by | 2.4k views

2 Answers

+6 votes
Best answer


L={ab, aba , abaa  ,abab  ,ababb,..........}

The minimum number of states of the non-deterministic finite automaton which accepts the language =5

Hence,Option(c)5 is the correct choice.

edited by
@leen why do we need 4 state here can't we make a transaction on b in the 3rd state itself.

no. we ca't draw it in 3 states. According to you Nfa is

Now you can see it can accept string ababab which is not accepted by given grammar.

I understood this . I have one more confusion if we don't make 4th state as final and make transition on b and accept in 3rd state only would that be a problem. ?

could you please write 3-4 strings of this lang after union of them then i would be able to understand it easily.and that will help me to understand you above comment diagram easily.

L1={ ababn |n≥0}  

The strings accepted by L1={aba , abab , ababb , ababbb..........    }                            

L2={ aban |n≥0}   

The strings accepted by L1={ab , aba , abaa , abaaa..........    }        


Now what is L1 ∪ L2 ?

L1 ∪ L2 is a language which is accepted by L1 or L2.

L1 ∪ L2={ ababn |n≥0}  ∪  { aban |n≥0}   

The strings accepted by L1 ∪ L={ab , aba , abaa , abab , ababb , abaaa..........    }        

state q3 required to accept minimum length string ab.

state q4 required because we can't able to accept abb here. we can't draw self loop for both a and b at state q3.

@leen Thank you so much for your response ...I appreciate it

you are most welcome smiley


I think abaab should not belong to L


Yessad i did mistake.

@leen there is correction your FA it is accepting abaab which is not the string in language

Praveen Saini Number of states should be 5 here. Right?

@yes correction required.I will update soon.

Praveen Saini  Sir please check  this


yes now it is correct update in answer


Thank You sirsmiley

0 votes

answer : 4

Correct me if I am wrong

i think your nfa is right.
your NFA accepting rejecting string "abaab" also so wrong
no his nfa accept abaa*b . u ignore loop .
ok I got it in case of NFA it is fine
Yes, This NFA wrongly accepts the string abaaaaabbb.. which does not belong to L

Answer is wrong

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,522 answers
95,372 users