Is $(r^*)^* = r^*$?

59 Views Asked by At

If $r$ is a regular expression, is it always true that $(r^*)^* = r^*$?

I've been trying to come up with simple examples and to me it seems like the answer is yes but I'm not quite sure. How would I justify this?

1

There are 1 best solutions below

0
On

The answer is yes.

If a word satisfies $r^{*}$ then it satisfies $(r^{*})^{*}$ because it is exactly one copy of a word that satisfies $r^{*}$.

If a word $w^{'}$satisfies $(r^{*})^{*}$ then it is $m$ copies of a word $w$ that satisfies $r^{*}$ where $m\ge 0$.

The word $w$ is $n$ copies of a word that satisfies $r$ where $n\ge 0$.

Therefore, $w^{'}$ is $nm$ copies of a word that satisfies $r$ which satisfies $r^{*}$.