UGC NET CSE | December 2012 | Part 3 | Question: 47

Question

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

• A. 3
• B. 4
• C. 5
• D. 6

Answer 1

L={ababⁿ∣n≥0}∪{abaⁿ∣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.

Comments

@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.

---

L₁={ ababⁿ |n≥0}  

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

L₂={ abaⁿ |n≥0}   

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

                               

Now what is L₁ ∪ L₂ ?

L₁ ∪ L₂ is a language which is accepted by L₁ or L_2.

L₁ ∪ L₂={ ababⁿ |n≥0}  ∪  { abaⁿ |n≥0}   

The strings accepted by L₁ ∪ 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 

---

I think abaab should not belong to L

---

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

Answer 2

answer : 4

Correct me if I am wrong

Comments

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

---

@sh!va thanks your point makes a difference here  now i got it