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

test for string a and epsilon we can easily get answer C

Answer 2

q0 is the initial state. q1 and q2 are the final states. String a  is accepted. 

Option a) doesn't generate string a.

option b) generates string b which is not accepted by the finite automata.

option d)  doesn't generates string a.

 

therefore option c is the answer.