A bijection between all regular expressions of alphabet $\Sigma$ and the natural numbers $\mathbb N$

Question

I have been asked to form a method for enumerating all regular expressions generated by the finite alphabet $\Sigma$, denoted by $\newcommand{\RE}{\operatorname{RE}}\RE(\Sigma)$. The set of all regular expressions over a certain alphabet is defined as follows.

Let $\Sigma$ be an alphabet and define the alphabet for regular expressions as $\newcommand{\set}[1]{\left\{ #1 \right\}}\Sigma_{\RE} = \Sigma \cup \set{\epsilon, \varnothing, +, \ast, (, )}$. Then

1. $\epsilon \in \RE(\Sigma)$
2. $\varnothing \in\RE(\Sigma)$
3. $\alpha\in\Sigma \Rightarrow \alpha \in \RE(\Sigma)$
4. $r, s \in \RE(\Sigma) \Rightarrow (r + s) \in \RE(\Sigma)$
5. $r, s \in \RE(\Sigma) \Rightarrow (rs) \in \RE(\Sigma)$
6. $r\in \RE(\Sigma) \Rightarrow r^* \in \RE(\Sigma)$

I guess what I now need to do is go over all of these cases one by one, and assign a natural number for each of them (and their combinations)? I'll just do this using the function $\newcommand{\Nset}{\mathbb{N}}f : \RE(\Sigma) \to \Nset$.

We start by mapping the base cases to some natural numbers:

1. $f(\epsilon) = 1$
2. $f(\varnothing) = 2$
3. if $\newcommand{\abs}[1]{\left\lvert #1 \right\rvert} N_\Sigma = \abs\Sigma$ is the size of the alphabet, and $\newcommand{\perm}[1]{\left\langle #1 \right\rangle}\perm{\alpha_i}_{i=1}^{N_\Sigma}= \Sigma$, then $f(\alpha_i) = i + 2$.

We have now used up the natural numbers from $1$ to $\abs\Sigma + 2$. Then there are the arbitrary unions, concatenations and concatenation closures still to think about. The problem is, I don't know where to begin dealing with these (effectively).

Is there some constructionist or inductive method to this, that I should be aware of? I have very little experince with these sorts of approaches.

Answer 1

It suffices to observe that a regular expression is a word on the alphabet $\newcommand{\RE}{\operatorname{RE}}\Sigma_{\RE}$. It follows that the set of regular expressions is a subset of $\Sigma_{\RE}^*$. Now, since $\Sigma_{\RE}$ is finite, the free monoid $\Sigma_{\RE}^*$ is countable, and thus the set of regular expressions is countable.