GATE IT 2006 | Question: 5

Question

Which regular expression best describes the language accepted by the non-deterministic automaton below?

• A. $(a + b)^* \ a(a + b)b$
• B. $(abb)^*$
• C. $(a + b)^* \ a(a + b)^* \ b(a + b)^*$
• D. $(a + b)^*$

Comments

why this question was asked 😅

---

😀

---

1. option $(D)$ is wrong as it genrate $\epsilon,a,b$ which is not accepted by nfa. 
2. Option $(C)$ is wrong, it generates $ab$, which is not accepted by nfa
3. . Option $(B)$ generates $\epsilon$, it won't generate $aab$, so it's also wrong.

So option $(a)$ is correct.

Answer 1

A is the answer.

Say $s_1, s_2 , s_3$ and $t$ are the states (in sequence) with $s_1$ being the start state

$s_1= \epsilon + s_1a + s_1b = \epsilon +s_1(a+b) = (a+b)^*$ [using Arden's theorem  $R= Q+RP$ , then $R= QP^*$][$\epsilon$ because of being the start state]

$s_2 = s_1a = (a+b)^*a$

$s_3= s_2a+s_2b = s_2(a+b) = (a+b)^*a(a+b)$

$t= s_3b= (a+b)^*a(a+b)b$

$t$ is final state so regular expression is $(a+b)^*a(a+b)b$

Comments

 

s1=ϵ+s1a+s1b=ϵ+s1(a+b)

The way we are writing the equations for each state is how many ways exist through which we can reach that particular state.

So,for $_{S1}$ , any length string will lead to state $_{S1}$ , will the equation not be S1=ϵ+S1$(a+b)^{*}$ , though final ans and solution to this equation remains same. @ Praveen Saini sir

---

@ Gaganjot _Kaur NFA and DFA are equal in power ,so you can apply in both DFA and NFA( includes $\epsilon$-NFA) . Arden's Lema will fetch you the regular expression for $\epsilon$-NFA because

$\epsilon$-NFA$ \rightarrow$ DFA (same power )

---

Easy Way:-

If we carefully notice, every string must end with $b$

1. $(a+b)^∗ a(a+b)b$ → TRUE
2. $(abb)^∗$   → Does not generate $aab$ →  FALSE
3. $(a+b)^∗ a(a+b)^∗ b(a+b)^∗$ →   Can end with $a$ → FALSE
4. $(a+b)^∗$ → Can end with $a$ → FALSE

Answer 2

Another quick approach of solving this question for keen observers :-

asterisk (*)  or  Kleene star. 

From the given NFA we can see EPSILON is not accepted in its language. 

When power of kleene closure taken "Zero". 

Option A. Has two paths aab or abb to reach final state. So, it is True✅

Option B.  when power of kleene closure zero then option B becomes epsilon which is not accepted by the NFA. 

Option C. when power of kleene closure is zero regular expression produces only string ab which is not accepted by the NFA. So option C is also false. 

Option D. When power of kleene closure is zero the regular expression produces Epsilon which is not accepted by the NFA. So the option d is also false. 

 

Answer 3

the first S represents (a+b)^*

and the next 2 states are S so they are same as S(first state) 

that is output of 2,3 states are generated by first S, that means we can combine those 3 states and finally make S as final state 

which lead to option D that is (a+b)^*

Answer 4

• option b and option d genrate null so it is false.becz it is not accepted by finite autometa
• option c genrate string ab which is also false

 so option a is true

Answer 5

The given NFA accepts all the strings that contains at least 1 ‘a’ and ends with ‘b’

• A.  is the answer 
• B. it does not accept string starting with b while our NFA accepts string starting with both ‘a’ and ‘b’  (Hence False)
• C. this expression accepts strings ending with ‘a’ (Hence False)
• D.  Same as option C (Hence False)

Answer 6

here I can see A is the answer as the first step we can go any no of a and b and then just follow the steps and concatenate those.