Assuming that Σ = {a, b}
, I want to find out the regular expression (RE) Σ*
(that being the set of all possible strings over the alphabet Σ
).
I came up with below two possibilities:
(a+b)*
(a*b*)*
However, I can't decide by myself which RE is correct, or if both are bad. So, please tell me the correct answer.
The +
operator is typically used to indicate union (|
, "or") in academic regular expressions, not "one or more" as it typically means in non-academic settings (such as most regex implementations).
So, a+b
means [ab]
or a|b
, thus (a+b)*
means any string of length 0 or more, containing any number of a
s and b
s in any order.
Likewise, (a*b*)*
also means any string of length 0 or more, containing any number of a
s and b
s in any order.
The two expressions are different ways of expressing the same language.