= Solution
Treat the fixed letters $a_1,\ldots,a_n$, the empty-language and empty-word symbols, and the punctuation of expressions as a finite token alphabet. In the usual syntax allowing parentheses, union, concatenation, and star, the following <context-free grammar> generates exactly the syntactically valid <regular expressions>:
$$
E\to\varnothing\mid\varepsilon\mid a_1\mid\cdots\mid a_n
\mid(E)\mid E+E\mid EE\mid E^*.
$$
Structural induction proves that every generated string is an expression and that every expression has a derivation. Grammar ambiguity does not affect the <context-free language> assertion.
If the language of these expressions were a <regular language>, its intersection with the regular token language consisting of some opening parentheses, then $a_1$, then some closing parentheses would be regular. That intersection is exactly
$$
\{\mathtt{(}^{\,r}a_1\mathtt{)}^{\,r}:r\ge0\}.
$$
The <pumping lemma for regular languages> contradicts regularity: a sufficiently long opening-parenthesis prefix forces a pumpable segment wholly within that prefix, and pumping it changes the two parenthesis counts unequally. Hence \b[the expression syntax is context-free but not regular]. This conclusion concerns the strings describing expressions, not the languages those expressions denote; it uses the usual concrete syntax with arbitrary nested parentheses.
Back to article page
