= Solution
An <alphabet> $\Sigma$ is a finite nonempty set of symbols. A <word over an alphabet> is a finite sequence of symbols from $\Sigma$, including the empty word $\epsilon$; the set of all words is $\Sigma^*$. A <formal language> over $\Sigma$ is any subset $L\subseteq\Sigma^*$.
A <regular expression> is defined recursively from $\varnothing$, $\epsilon$, and the individual symbols $a\in\Sigma$ by the operations of finite union, concatenation, and <Kleene star>. Its language is defined by
$$
L(\varnothing)=\varnothing,\qquad
L(\epsilon)=\{\epsilon\},\qquad
L(a)=\{a\},
$$
$$
L(R\mid S)=L(R)\cup L(S),\qquad
L(RS)=L(R)L(S),\qquad
L(R^*)=L(R)^*.
$$
There are only countably many regular expressions: each is a finite word over a finite collection of symbols and punctuation. On the other hand, for every nonempty finite alphabet, $\Sigma^*$ is countably infinite, so its <power set> $\mathcal P(\Sigma^*)$ is uncountable by the <Cantor theorem>. Thus there are uncountably many languages but only countably many languages denoted by regular expressions. Consequently
$$
\boxed{\text{some languages over }\Sigma\text{ are not regular}}.
$$
Back to article page
