in Theory of Computation edited by
6,453 views
23 votes
23 votes

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^*)^*$
in Theory of Computation edited by
by
798 813 839
6.5k views

4 Comments

edited by
option c  can  never form 'a' but our question expression will be
8
8
how  option d     generate (a+b+c)*
0
0

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

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

Subscribe to GO Classes for GATE CSE 2022

5 Answers

41 votes
41 votes
 
Best answer
  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$

Correct Answer: C.

edited by
by
212 350 586

5 Comments

Hi @Praveen Saini ji,

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

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

eg:

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

@Praveen Saini @abhishekmehta4u

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

0
0
We can't say that.

For ex. a*b* can generate ab but a* + b* can't generate it.
1
1
11 votes
11 votes
((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
9 votes
9 votes
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
0
0
0 votes
0 votes
as in option c ab cant be separated so we cant generate a,or b.

so option c
by
2 8 12
0 votes
0 votes

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

by
12 46 147
Answer:

Related questions