Regular Expressions

Definition

A sequence of characters that defines a search pattern

$R$ is a regular expression if $R$ is:

1. $a$ for some $a$ in the alphabet $\Sigma$
2. $ϵ$
3. $\varnothing$
4. $(R_1\cup R_2)$, where $R_1$ and $R_2$ are regular expressions
5. $(R_1\circ R_2)$ where $R_1$ and $R_2$ are regular expressions
6. $(R_1^{\ast })$ where $R_1$ is a regular expression