The Gateway to Computer Science Excellence
+23 votes

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

Which one of the regular expressions given below defines the same language as defined by the regular expression $R$ ?

  1. $(a(ba)^* + b(ab)^*)(a + b)^+$
  2. $(a(ba)^* + b(ab)^*)^*(a + b)^*$
  3. $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^*$
  4. $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^+$
in Theory of Computation by Boss (16.3k points)
edited by | 3.6k views
B and D are completely wrong bcz not generate min string aa or bb  . and A is wrong bcz generate string  abab  which is not part of given R.E

5 Answers

+43 votes
Best answer

$R = (a+b)^*(aa+bb)(a+b)^*$

Having NFA:

Equivalent DFA:

Which is equivalent Transition graph [by removing transition from $q1$ to $q2$ and $q2$ to $q1$ but does not effect on language, be careful]

That is equivalent to:

Which is equivalent to:

Which is equivalent to:

So, equivalent regular expression is $[a(ba)^*(a+bb) + b(ab)^*(b+aa)](a+b)^*$

So, option C is answer.

by Veteran (57k points)
edited by

@Praveen Saini ji,   Long but awesome  approach.  Thank You. :)

i am not getting your 3rd digram can u please explain
that $(a+b)^*$ is bcoz of loop(closure) at state q3.
Can't get why we are adding aa as a transition from q1 to q3 and bb as transition from q2 to q3 in the 3rd diagram?


from q0 to q3 we accept abb and baa (diagram first)

when the array is removed (diagram 3) then it also accept abb and baa . so we need to add it.

+56 votes
Another quick approach of solving this question for keen observers :-

Observe that $aa$ or $bb$ is minimal string that is possible in first Regular Expression $(a + b)^* (aa + bb) (a + b)^*.$

(A) We can have $ba$ or $ab$ as minimal strings which is not possible in $(a + b)^* (aa + bb) (a + b)^*$

(B) We can have empty string, which is not possible in $(a + b)^* (aa + bb) (a + b)^*.$

(D) Minimum string length is $3,$ $aa$ or $bb$ is not possible in this RE.

This rules out options A, B and D. So, option C must be the answer.
by Boss (41.9k points)
ur approch is time consuming when none of the above is given as one option . bdw its good when none of the above not given...
Approach of solving question is decided based on looking at question first.
for the option  [D] we can not genrate three length string like { aaa,baa,aab}

which we can generate from R = (a + b)* (aa + bb) (a + b)* so this makes option D false
came here looking for exactly this kind of answer. the 'best answer' is quite difficult since we may not get a unique RE for a given DFA, and that itself can consume lot of time.
+5 votes

> "abab" does not belong to the language but accepted by A & B. (Cancel them)
"aa" belongs to the language, not accepted by D. Hence C is the ans. 

by Boss (12.4k points)
I think the language accepted by D are aaa,abbb,baa,bbbb not aa
+2 votes
B produces null. The given expr does not. So, B is eliminated.

A accepts abab. The given expr does not. So, A is eliminated. [P.S.: (a+b)+ does not produce null.]

The first bracketed part of both C and D produce a string with a substring of aa or bb, which is asked by the expr. But after that (a+b)+ cannot produce null. So, D is eliminated.

C is the answer.
by (369 points)
0 votes
We will eliminate a given option

1--if it generates a new string that is not generated by given expression


2--if it doesn't generate a string generated by the given expression

Option a- generates "ab" Which is not generated by given expression. So eliminated

Option b- same reason as option a

Option d- can't generate "bb" Which is generated by given expression. So eliminated.

So we are left with option c.Hence it is the answer.

If none of the above is given as a option, we have to check the option we are left with intuitively..
by Active (4.4k points)

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
50,737 questions
57,313 answers
105,046 users