The meaning of regular expressions

We now know what regular expressions are but what do they mean?

For this purpose, we shall first define an operation on languages called the Kleene star. Given a language $L\subseteq \Sigma^*$ we define

$$L^* = \{ w_0w_1\dots w_{n-1} \mid n\in\mathbb{N}\wedge \forall i<n. w_i \in L \}$$

Intuitively, $L^*$ contains all the words which can be formed by concatenating an arbitrary number of words in $L$. This includes the empty word since the number may be 0.

As an example consider $L=\{\textrm{a},\textrm{ab}\}\subseteq \{\textrm{a},\textrm{b}\}^*$:

$$L^* = \{\epsilon,\textrm{a},\textrm{ab},\textrm{aab},\textrm{aba},\textrm{aaab},\textrm{aaba},\dots\}$$

You should notice that we use the same symbol as in $\Sigma^*$ but there is a subtle difference: $\Sigma$ is a set of symbols but $L\subseteq \Sigma^*$ is a set of words.

Alternatively (and more abstractly) one may describe $L^*$ as the least language (wrt $\subseteq$) which contains $L$ and the empty word and is closed under concatenation:

$$w \in L^* \wedge v\in L^* \implies wv \in L^*$$

We now define the semantics of regular expressions: To each regular expression $E$ over $\Sigma$ we assign a language $L(E)\subseteq \Sigma^*$. We do this by induction over the definition of the syntax:

1. $L(\emptyset) = \emptyset$
   
2. $L(\epsilon) = \{\epsilon\}$

3. $L(\textbf{x}) = \{ x \}$
   where $x\in\Sigma$.

4. $L(E+F) = L(E)\cup L(F)$

5. $L(EF) = \{ wv \mid w\in L(E) \wedge v\in L(F) \}$

6. $L(E^*) = L(E)^*$

7. $L(\textbf{(}E\textbf{)})=L(E)$

Subtle points: in 1. the symbol $\emptyset$ may be used as a regular expression (as in $L(\emptyset)$) or the empty set ( $\emptyset=\{\}$). Similarily, $\epsilon$ in 2. may be a regular expression or a word, in 6. $*$ may be used to construct regular expressions or it is an operation on languages. Which alternative we mean becomes only clear from the context, there is no generally agreed mathematical notation ¹to make this difference explicit.

Let us now calculate what the examples of regular expressions from the previous section mean, i.e. what are the langauges they define:

$\epsilon$

$$L(\epsilon) = \{\epsilon\}$$

By 2.

$\textrm{hallo}$

Let's just look at $L(\textrm{ha})$. We know from 3:

$$L(\textrm{h}) = \{ \textrm{h}\}$$

$$L(\textrm{a}) = \{ \textrm{a}\}$$

Hence by 5:

$$L(\textrm{ha}) = \{ wv \mid w\in\{\textrm{h}\} \wedge v\in \{\textrm{a}\}\}$$

$$ = \{ \textrm{ha} \}$$

Continuing the same reasoning we obtain:

$$L(\textrm{hallo}) = \{\textrm{hallo}\}$$

$\textrm{hallo}+\textrm{hello}$

From the previous point we know that:

$$L(\textrm{hallo}) = \{\textrm{hallo}\}$$

$$L(\textrm{hello}) = \{\textrm{hello}\}$$

$$$$

Hence by using 4 we get:

$$L(\textrm{hallo}+\textrm{hello}) = \{\textrm{hallo}\}\cup \{\textrm{hello}\}\}$$

$$ = \{\textrm{hallo},\textrm{hello}\}$$

$\textrm{h}(\textrm{a}+\textrm{e})\textrm{llo}$

Using 3 and 4 we know

$$L(\textrm{a}+\textrm{e}) = \{ \textrm{a},\textrm{e} \}$$

Hence using 5 we obtain:

$$L(\textrm{h}(\textrm{a}+\textrm{e})\textrm{llo}) = \{uvw \mid u\in L(\textrm{h}) \wedge v\in L(\textrm{a}+\textrm{e}) \wedge w \in L(\textrm{llo}) \}$$

$$= \{uvw \mid u\in \{\textrm{h}\} \wedge v\in\{ \textrm{a},\textrm{e} \} \wedge w \in \{\textrm({llo}\} \}$$

$$= \{\textrm{hallo},\textrm{hello}\}$$

$\textrm{a}^*\textrm{b}^*$

Let us introduce the following notation:

$$w^i = \underbrace{ww \dots w}_{i \textrm{ times}}$$

Now using 6 we know that

$$L(\textrm{a}^*) = \{ w_0w_1\dots w_{n-1} \mid n\in\mathbb{N}\wedge \forall i<n. w_i \in L(\textrm{a}) \}$$

$$= \{ w_0w_1\dots w_{n-1} \mid n\in\mathbb{N}\wedge \forall i<n. w_i \in \{\textrm{a}\} \}$$

$$= \{ \textrm{a}^n \mid n\in\mathbb{N}\}$$

and hence using 5 we conclude

$$L(\textrm{a}^*\textrm{b}^*) = \{ uv \mid u \in L(\textrm{a}^*) \wedge v \in L(\textrm{b}^*) \}$$

$$= \{ uv \mid u \in \{\textrm{a}^n \mid n\in\mathbb{N}\} \wedge v \in \{\textrm{a}^m \mid m\in\mathbb{N}\} \}$$

$$= \{ \textrm{a}^n\textrm{b}^m \mid m,n \in \mathbb{N}\}$$

I.e. $L(\textrm{a}^*\textrm{b}^*)$ is the set of all words which start with a (possibly empty) sequence of as followed by a (possibly empty) sequence of bs.

$(\epsilon+\textrm{b})(\textrm{ab})^*(\epsilon+\textrm{a})$

Let's analyze the parts:

$$L(\epsilon+\textrm{b}) = \{ \epsilon, \textrm{b} \}$$

$$L((\textrm{ab})^*) = \{ \textrm{ab}^i \mid i \in\mathbb{N}\}$$

$$L(\epsilon+\textrm{b}) = \{ \epsilon, \textrm{b} \}$$

Hence, we have

$$L((\epsilon+\textrm{b})(\textrm{ab})^*(\epsilon+\textrm{a})) = \{... ...on, \textrm{b} \} \wedge i\in\mathbb{N}\wedge v \in \{ \epsilon, \textrm{b} \}$$

In english: $L((\epsilon+\textrm{b})(\textrm{ab})^*(\epsilon+\textrm{a}))$ is the set of (possibly empty) sequences of interchanging as and bs.