Question

Consider the regular expression :

$R=(a+b{)}^{\ast }(aa+bb\left)\right(a+b{)}^{\ast }$

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

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

Answer 1

The correct option is D

In option (a) S3 and S4 together act as a permanent accept and can be therefore be collapsed into a single permanent accept state as shown below




This machine clearly accepts all strings containing the substring 'aa' or 'bb', which is same as regular expression R.