Regular Expressions

A regular expression is a string that matches patterns according to specific rules. Regular expressions can be used to parse regular languages.

Syntax §

For the purposes of these notes, the following syntax is used for regular expressions:

• $a$ - match the expression $a$,
• $a\ast$ - match any number of $a$ next to each other, including 0,
• $a|b$ - match either $a$ or $b$. Brackets can be used to group patterns within an expression.

Info

This definition differs from the common implementations of Regular Expressions in programming languages, which typically include helpful (though not necessary) shorthands such as $?$ and $+$.

Defining Languages §

Languages can be defined by regular expressions: The language defined by a regular expression $p$, $\mathcal{L}(P)$ is given by the set of all words over $\Sigma$ that match $p$. $\mathcal{L}(P)=\{s\in \Sigma \ast |smatchesp\}$.