6,453 views

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

1. $(a^* + b^* + c^*)^*$
2. $(a^*b^*c^*)^*$
3. $((ab)^* + c^*)^*$
4. $(a^*b^* + c^*)^*$

edited by
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)*) = Σ*.

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

### Subscribe to GO Classes for GATE CSE 2022

1. $(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$ ]
2. $(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$
3. $((ab)^\ast + c^\ast)^\ast =(ab+c+\epsilon +abab+\ldots)^\ast = (ab+c)^\ast$
4. $(a^\ast b^\ast + c^\ast)^\ast = (a^\ast+b^\ast+c^\ast+\ldots)^\ast =(a+b+c+\ldots)^\ast =(a+b+c)^\ast$

by
212 350 586

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)^*$

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.
((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).
by
28 53 89
Alone string 'a'  or string 'b' can't produce by Option C So Option C is Ans.
by
123 219 338

### 1 comment

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

so option c
by
2 8 12

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

by
12 46 147