edited by
8,780 views
28 votes
28 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^*)^*$
edited by

5 Answers

Best answer
46 votes
46 votes
  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
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).
Answer:

Related questions