What is the difference between regular expression $(x + y)^*$ and $(x^*y^*)$?

Question

What is the difference between regular expression $(x + y)^*$ and $(x^*y^*)$ ?

Answer 1

If $x$ and $y$ are words on the alphabet $A$, the regular expression $(x + y)^*$ denotes the submonoid of $A^*$ generated by $x$ and $y$. Thus $$ (x + y)^* = \{1, x, y, xx, xy, yx, yy, xxx, xxy, xyx, \ldots\} $$ where $1$ is the empty word. The regular expression $x^*y^*$ denotes the product of $x^*$ by $y^*$. Therefore $$ x^*y^* = \{x^ny^m \mid n \geqslant 0, m \geqslant 0\} $$ Thus $(x + y)^* = x^*y^*$ if and only if $xy = yx$, which is known to be equivalent to the fact that $x$ and $y$ are powers of the same word, that is $x = u^p$ and $y = x^q$ for some $p,q \geqslant 0$.

Answer 2

have you read the manual ?

• +: 1 or more
• *: 0 or more
• ?: 0 or 1 (if part of your expression above: ambiguous).

So:

• (x+y)* can produce (), xy, xxxy, xyxxy, etc. Never more than 1 y in a row, any number (>0) of x between.
• (x*y*) can produce (), x, y, xx, yy, xyy, etc. I.e., 0 or more x, then 0 or more y.

Answer 3

There seems to exist several syntaxes for regular expressions which is why one should be a bit careful. What I would guess is that $+$ in this context means "or". In many programming languages "or" is instead written as a vertical line | so that can give some confusion.

If my interpretation is correct then $(x+y)^*$ means " 'either x or y' repeated any number of times" and $x^*y^*$ means x repeated any number of times followed by y repeated any number of times.

The difference is that the first one can find strings which have $x$s coming after the first $y$. The second one the order is important: first any number of $x$s and then as many $y$s we can find.

Examples:

$xyxyxy$ should only be matched by the first one but $xxyyy$ by both.