What are regular expressions?

We assume as given an alphabet $\Sigma$ (e.g. $\Sigma = \{ \textrm{a},\textrm{b},\textrm{c},\dots,\textrm{z}\}$) and define the syntax of regular expressions (over $\Sigma$)

1. $\emptyset$ is a regular expression.

2. $\epsilon$ is a regular expression.

3. For each $x\in\Sigma$ , $\textbf{x}$ is a regular expression. E.g. in the example all small letters are regular expression. We use boldface to emphasize the difference between the symbol a and the regular expression a.

4. If $E$ and $F$ are regular expressions then $E+F$ is a regular expression.

5. If $E$ and $F$ are regular expressions then $EF$ (i.e. just one after the other) is a regular expression.

6. If $E$ is a regular expression then $E^*$ is a regular expression.

7. If $E$ is a regular expression then $(E)$ is a regular expression.

These are all regular expressions.

Here are some examples for regular expressions:

• $\epsilon$

• hallo

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

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

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

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

As in arithmetic they are some conventions how to read regular expressions:

• $*$ binds stronger then sequence and $+$. E.g. we read $\textrm{a}\textrm{b}^*$ as $\textrm{a}(\textrm{b}^*)$. We have to use parentheses to enforce the other reading $(\textrm{ab})^*$.
• Sequencing binds stronger than $+$. E.g. we read $\textrm{ab}+\textrm{cd}$ as $(\textrm{ab})+(\textrm{bc})$. To enforce another reading we have to use parentheses as in $\textrm{a}(\textrm{b}+\textrm{c})\textrm{d}$.