GATE CSE 2007 | Question: 74

Question

Consider the following Finite State Automaton:

The language accepted by this automaton is given by the regular expression

• A. $b^*ab^*ab^*ab^*$

• B. $(a + b)^*$

• C. $b^*a(a+b)^*$

• D. $b^*ab^*ab^*$

Comments

We can reduce given automata to this-

 

---

Approach:

Sometimes there is a tricky question where even this  type of FA accept (a+b)* , but here b not accepted so that isn't possible.

We can have any number of b then a, q3 is unreachable so forget about it. For q1 and q2 we have transition for all symbol and it's within these two states so it will accepts everything after this. So b*a(a+b)*

---

The smallest string the NFA accepting is “a” . Now option elimination.

 

Answer 1

The answer is C.

You can see that both the states, $q_1$ and $q_2$ are final and are accepting $(a+b)^*$.

[Edit]

1. $q_3$ is unreachable state, hence it can be removed.
2. States $q_1$ and $q_2$ are indistinguishable, so, they can be merged. 

Comments

Abhrajyoti00

yes , btw both are generating the same strings .

---

My earlier eg was catching the first $a$.

Your eg was catching the middle $a$.

Even $(a+b)^*ab^*$ is also correct (It is catching the last $a$).

All mean: Atleast 1 $a$

---

@Abhrajyoti00 nice point

Answer 2

given DFA accept a but option A and D cant so A and D are eliminated 
option B accept epsilon but given DFA cant accept epsilon so B eliminated 
Hence Ans is C

q3 i unreachabl state wo we remove it now both q1 and q2 are equivalent so they can combine now we easily find regular expression for it : b*a(a+b)*

Answer 3

I will proceed with elimination of options
Option A: wrong because, string "ba" is accepted by given DFA. R.E given here can't generate it.
Option B: epsilon can't be accepted by given DFA. Given R.E generates epsilon
Option D: Same reason as option A. As "ba" can't be generated here too. The least it can generate are aa,baa,bbaa... so on..

Option C is correct. How???

After reaching q1, the DFA can accept any string generated by the alphabet{a,b}. b* is obvious from the given figure. to reach q1 we need atleast one a. Hence, b*a(a+b)^* is correct R.E

Comments

minimal string accepts by A&D are 3a's, 2 a's but from the figure, we can see that string contain one 'a'  is minimal.

Answer 4

The answer is C

It is very clear from the diagram that q3 is unreachable. Hence it can be removed.

After its removal the diagram looks like

Based on Arden’s Theorem of converting DFA to Regular Expression,

It states that,

Let P and Q be two regular expressions over ∑.

If P does not contain a null string ∈, then,

R = Q + RP has a unique solution i.e. R = QP*

STEPS for constructing REGEX

1. Form equation for each state and add  ∈ in the initial state equation
2. Bring final state in the form of R = Q + RP

In case of having multiple final state,

1. Write Regex for each final state and add them all to arrive at the final solution

For the above problem,

q0 = q0.b + ∈  → 1 (Epsilon is added as part of step 1)

q1 = q0.a + q1.b + q2.a  -→ 2

q2 = q1.a + q2.b → 3

Now Compare equation 1 with R = Q+RP , (R = q0 ; Q= ∈ ; P = b)

thus q0 = ∈ . b*

q0 = b*  

Substituting q0 value in equation 1, we get

q1 = b*.a + q1.b + q2.a → 4

Since our problem contains two final state add the two state to arrive at the final solution

ADD equation 2 and 4

q1 + q2 = b*.a + q1.b + q2.a + q1.a + q2.b

q1 + q2  = b*.a + q1(a + b) + q2 (a+b)

q1 + q2  = b*.a + (q1 + q2)(a+b) → 5

Compare equation 5 with R = Q+RP , (R = q1 + q2 ; Q= a.b* ; P = (a+b)  )

Thus,

q1+q2 = b*.a(a+b)*   ///// R = Q + RP has a unique solution i.e. R = QP*

Comments

@Krithika Kumaran shouldn’t it be ‘add equation 4 and 3’?