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

Ans.C can't generate single a,b 

---

option C is forcing  to generate ab together

---

if you get single a,b,c , it acts like god and hence you can get (a+b)* definately
in option c, you cannot get single a and b due to (ba)* coming in pair.

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

@Praveen sir :

 

(a*b* + c*)* = (a*+b*+c*+...)* =(a+b+c+..)* =(a+b+c)*!!!! string (a+b+c)* means any string of a,b,c..but String bac can not be generated by (a*b* + c*)*!!!!

---

@_pyuri  by taking *=3  then u can (a*b*+c*) (a*b*+c*)(a*b*+c*)  in first u take 'b' and from second u take 'a' and from third u take 'c' only then u got 'bac'

---

thanks

---

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.

---

@ayushsomani We can say, $(a^{*}b^{*})^{*}=(a+b)^{*}$

---

why ai like chat gpt,gemini giving other answe😩

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

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

Answer 5

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

so option c