The Gateway to Computer Science Excellence
+31 votes
2.4k views

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

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

in Theory of Computation by
edited by | 2.4k views

7 Answers

+22 votes
Best answer

DFA given in option A

Here, $S_3$ and $S_4$ are equivalent states and can be minimized.

This results in DFA given in:

https://gateoverflow.in/3523/gate2007-it_71

by
edited by
0
Link not working!
+25 votes
C. Is false since abb not accepted

D. Is false since as or bb not accepted

B.is false since it is not DFA

A. Is the ans .. S3 and S4 are similar States..minimum no.of states are 4
by
0
right
+2
Option C will also not accept baa, abb etc.
+9 votes

A)  as it accepts anything (aa or bb )anything
So aa ,bb, aaa,aaaa bbb,bbbb,bbbbbb,bbaaaababba
ababababaababababa or abababababbb will be accepted
and only A satisfies.
Correct if Wrong,

by
+3 votes

lets try by elimination:

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

(C.) it is not accepting abb which is in language

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

coming to option (A.) it accepts anything containing aa/bb

by
0 votes

(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 

by
0 votes

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!

by
–2 votes
Option a and c both seems right
by
+2
I was also stuck between these two, but C does not accept 'abb' or 'baa'.
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,513 answers
201,931 comments
95,357 users