1
$\begingroup$

Let $a,b,c$ be regular expressions. Prove by transformation that $(a^*b^*+c)^* \equiv (a+ (b+c)^*)^*$

I tried to start with the second term

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

but am stuck here. Can you please help me to go on?

Thanks!

[Edit:]

Transformation rules:

  • $a + b = b + a$
  • $(a + b) + c = a + ( b + c)$
  • $\epsilon a = a = a \epsilon$
  • $(a b) c = a (b c)$
  • $a(b + c) = ab + bc$
  • $(a + b)c = ac + bc$
  • $\epsilon^* = \epsilon$
  • $(a^*)^* = a^*$
  • $(\epsilon + a)^* = a^*$
  • $(a^*b^*)^* = (a+b)^*$
  • $(ab)^*a = a(ab)^*$
  • 0
    @Ehsan, yes, the first one allows `a`, `aba`, `ababa` etc; the second one allows `a`, `aab`, `aabab` etc. i.e. they are different regular expressions.2012-05-03

1 Answers 1

2

Here is the solution: $(a + ((b+c)^*))^* = (a^*(b+c)^*)^*=(a+(b+c))^*$ $=((a+b)+c)^*=((a+b)^*c^*)^*=((a^*b^*)^*c^*)^*=(a^*b^*+c)^*$

I used these rules:

  • $(a^*)^* = a^*$
  • $(a^*b^*)^* = (a+b)^*$
  • $(a + b) + c = a + ( b + c)$
  • 2
    You are right, Thanks.2012-05-03