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)^*$

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

Are we allowed to use same name for different states as in this question ? How do we write the transitions then??

---

you can rename them as per your choice.

---

Can we apply Arden's theorem on NFA as well?

---

yes we acn apply apply Arden's theorem on NFA

---

@abhishekmehta4u Sir, can we apply Arden's theorem on epsilon-NFA?

 

---

 

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

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 3

• 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 4

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)