1
$\begingroup$

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)^*$.

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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".

$\endgroup$
0

You must log in to answer this question.

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