GATE IT 2004 | Question: 7

Question

Which one of the following regular expressions is NOT equivalent to the regular expression $(a + b + c)^*$?

• A. $(a^* + b^* + c^*)^*$
• B. $(a^*b^*c^*)^*$
• C. $((ab)^* + c^*)^*$
• D. $(a^*b^* + c^*)^*$

Comments

option c  can  never form 'a' but our question expression will be

---

how  option d     generate (a+b+c)*

---

If r is a regular expression denoting a language L(r) over some alphabet Σ, and we have  Σ ⊆ L(r)  then  L((r)*) = Σ*.

Source: http://www.fbeedle.com/formallanguage/ch07.pdf

---

C is forcing us to have a and b together, so we cannot have only a or b.

Answer 1

• A. $(a^* + b^\ast + c^\ast)^\ast  = ( \epsilon + a+aa+ \ldots +b+bb+\ldots +c+cc + \ldots)^\ast = (a+b+c+ aa+\ldots + bb +\ldots +cc+\ldots )^\ast= (a+b+c)^\ast$ 
  [any combination of rest of $aa ,bb,cc,$ etc. already come in $(a+b+c)^\ast$ ]
• B. $(a^\ast b^\ast c^\ast)^\ast = (a^\ast+b^\ast+c^\ast +a^\ast b^\ast+b^\ast c^\ast+a^\ast c^\ast+ \ldots)^\ast=(a+b+c+\ldots)^\ast = (a+b+c)^\ast$
• C. $((ab)^\ast + c^\ast)^\ast =(ab+c+\epsilon +abab+\ldots)^\ast = (ab+c)^\ast$
• D. $(a^\ast b^\ast + c^\ast)^\ast = (a^\ast+b^\ast+c^\ast+\ldots)^\ast =(a+b+c+\ldots)^\ast =(a+b+c)^\ast$

Correct Answer: C.

Comments

Hi @Praveen Saini ji,

What do you want to show via intermediate expansion. If you can explain then it will be great help. 

---

$(a+b + more\:strings\:from \:combinations\: of\: \{a,b\})^* = (a+b)^*$

eg:

$(a+b+ab)^*= (a+b)^*$

---

@Praveen Saini @abhishekmehta4u

Can we say $a^{*}b^{*}$ = $a^{*}+b^{*}$?

---

We can't say that.

For ex. a*b* can generate ab but a* + b* can't generate it.

Answer 2

((ab)* + c*)* will not produce the strings where 'a' comes without 'b' and vice-versa. Therefore, language generated by option (c) is proper subset of language genrated by (a+b+c)* . Answer would be (C).

Answer 3

Alone string 'a'  or string 'b' can't produce by Option C So Option C is Ans.

Comments

best ans

Answer 4

as in option c ab cant be separated so we cant generate a,or b.

so option c

Answer 5

We try to genrate string a,b,c . For each expression .