I. Definition

Regular expressions describe languages by an algebra.

• They describe exactly the regular languages.
• If $E$ is a regular expression, then $L(E)$ is the language it defines.
• We’ll describe RE’s and their languages recursively.

<aside> 💡 Operations RE’s use three operations:

• • Union
• Concatenation
• • Kleene star

Order of precedence is * (highest), then concatenation, then + (lowest)

</aside>

Regular expressions describe syntax / grammar,

while regular languages describe semantics.

1. Basis

1. If $a$ is any symbol, then $a$ is a RE, and $L(a) = \{a\}$.
2. $ε$ is a RE, and $L(ε) = \{ε\}$.
3. $∅$ is a RE, and $L(∅) = ∅$.

2. Induction

1. If E1 and E2 are regular expressions, then $E_1+E_2$ is a regular expression,

   and $L(E_1+E_2) = L(E_1)\cup L(E_2)$.

2. If E1 and E2 are regular expressions, then $E_1E_2$ is a regular expression,

   and $L(E_1E_2) = L(E_1)L(E_2)$.

3. If E is a RE, then $E^*$ is a RE,

   and $L(E^) = (L(E))^$.

2. RE and FA

1. RE to ε-NFA - Thompson's Construction