Regular expression syntax over an alphabet

Let $\mathrm{\Sigma }$ be an alphabet. The set of regular expressions over $\mathrm{\Sigma }$ is the smallest class $\mathrm{Reg}(\mathrm{\Sigma })$ such that:

• $\mathrm{\varnothing }$, $\epsilon$, and every letter $a\in \mathrm{\Sigma }$ belong to $\mathrm{Reg}(\mathrm{\Sigma })$;
• whenever $R,S\in \mathrm{Reg}(\mathrm{\Sigma })$, the formal expressions $(R+S)$, $(RS)$, and $(R^{\ast })$ also belong to $\mathrm{Reg}(\mathrm{\Sigma })$.

Thus a regular expression is a finite formal expression tree built from the three base symbols $\mathrm{\varnothing },\epsilon ,a$ and the three constructors union, concatenation, and star.

• The definition is syntactic: two different expression trees may still denote the same language.

• Parentheses are part of the formal syntax, even when ordinary mathematical notation later suppresses some of them.