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$ ?

- $(a(ba)^* + b(ab)^*)(a + b)^+$
- $(a(ba)^* + b(ab)^*)^*(a + b)^*$
- $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^*$
- $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^+$

+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.

+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.

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.

+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.**

+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.

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.

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..

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..

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,313 answers

198,347 comments

105,046 users