edited by
13,908 views
44 votes
44 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)^+$
edited by

8 Answers

Best answer
65 votes
65 votes

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

Having,

Which is equivalent to the following Transition graph [by removing transition from $Q_1$ to $Q_2$ and $Q_2$ to $Q_1$ but does not affect the accepted language, be careful] and can be converted to an equivalent regular expression as shown below.

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

Option C is answer.

edited by
100 votes
100 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.
9 votes
9 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. 

4 votes
4 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.
Answer:

Related questions

42 votes
42 votes
7 answers
1
Ishrat Jahan asked Oct 30, 2014
7,776 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$?
47 votes
47 votes
4 answers
2
67 votes
67 votes
3 answers
4
Ishrat Jahan asked Oct 30, 2014
12,633 views
Consider the following grammars. Names representing terminals have been specified in capital letters.$$\begin{array}{llll}\hline \text{$G1$ :} & \text{stmnt} & \text{$\...