GATE IT 2007 | Question: 72

Question

Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$

Which deterministic finite automaton accepts the language represented by the regular expression $R$?

• A.
• B.
• C.
• D.

Comments

B → “ab”

C → “abb”

D → “aa”

---

B is still not a DFA coz of by the definition Dfa We can have exctly one transition from one state to any other state, but here in S3 there are 2 transitions on a which is not valid.

---

What is the proper way of solving these type of questions?  Is trial and error the only way?

---

@Gopal Deshmuk take strings which is accepting by the regular expression and check which string is accepted by the dfa is the easiest way .

Answer 1

(B.) it accepts ab which is not in the language

(C.) it is not accepting abb which is in language and also  Is false since  baa, abb not accepted

(D.) it is not accepting aa and bb which is in language

coming to option (A.) it accept 

Answer 2

Here, 

Option B: it generates a string like ab which is not a part of our language, hence rejected.

Option C and D: they don't even accept the minimal length strings aa and bb of our language, hence rejected.

Option A is thus the right answer!

Answer 3

Option a and c both seems right

Comments

I was also stuck between these two, but C does not accept 'abb' or 'baa'.

---

Yes they seems but they are not.