The Gateway to Computer Science Excellence
+4 votes
1.8k views

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 Veteran (105k points)
recategorized by | 1.8k views

2 Answers

+6 votes
Best answer

L={ababn∣n≥0}∪{aban∣n≥0} 

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.

by Boss (41k points)
edited by
0
@leen why do we need 4 state here can't we make a transaction on b in the 3rd state itself.
0

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.

0
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.
+1

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.

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

you are most welcome smiley

+1

I think abaab should not belong to L

+1

Yessad i did mistake.

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

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

0
@yes correction required.I will update soon.
+1

Praveen Saini  Sir please check  this

0


yes now it is correct update in answer

+1

Thank You sirsmiley

0 votes

answer : 4

Correct me if I am wrong

by Boss (32.5k points)
+1
i think your nfa is right.
+1
your NFA accepting rejecting string "abaab" also so wrong
0
no his nfa accept abaa*b . u ignore loop .
0
ok I got it in case of NFA it is fine
0
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
50,644 questions
56,516 answers
195,579 comments
101,142 users