+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

recategorized | 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
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

+1

I think abaab should not belong to L

+1

Yes 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 sir

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

+4 votes
5 answers
1
+3 votes
2 answers
2
+1 vote
4 answers
3
+1 vote
1 answer
4