# Transformation of a regular expression

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

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

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)^*$
-
What transformation rules are you using? – Ted May 3 '12 at 7:22
Sorry, I forgot to add them. Now they're there. – muffel May 3 '12 at 7:40
Isn't that last transformation rule untrue? (The first one gives abab...aba and the second one gives aab...ab) – huon May 3 '12 at 11:52
@dbaupp: star * allows zero or more repetitions so the second one haven't start with a. – Ehsan May 3 '12 at 12:21
@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. – huon May 3 '12 at 12:25

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)^*$$
• $(a^*)^* = a^*$
• $(a^*b^*)^* = (a+b)^*$
• $(a + b) + c = a + ( b + c)$
The step that introduces $(a^*(b^*c^*)^*)^*$ is unnecessary, and can be completely removed. – huon May 3 '12 at 12:11