The Gateway to Computer Science Excellence
+23 votes
3.6k views

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
–1
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
+3

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

0
i am not getting your 3rd digram can u please explain
+1
that $(a+b)^*$ is bcoz of loop(closure) at state q3.
0
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?
+1

pallaviamu

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)
+1
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...
+7
Approach of solving question is decided based on looking at question first.
0
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
0
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)
0
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

Or

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