I have the following regular expression

$$(ΣΣ)^∗ = \{w\mid w \text{ is a string of even length}\}.$$

The problem is that I don't quiet agree with the description of the regular expression. It is indeed a string of even length, but strings like 1000 are not allowed. $x^*$ means all the strings in the form xxxxxx... , but there is no way you can get 1000 with something in the form $(x)^*$.


1 Answer 1


In formal languages and automata theory sigma $\Sigma$ is used to represent the set of all characters in your language. So if the characters of your language are "$0$" and "$1$" then you can treat $\Sigma$ as $(0|1)$.

Your example then expands to $((0|1)(0|1))*$ which will match "1000".


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .