title: "Regular Expression"

Regular Expression

Definition. The regular expressions over an alphabet $\Sigma$ are defined inductively: $\emptyset$, $\varepsilon$, and each symbol $a \in \Sigma$ are regular expressions, and if $R_1$ and $R_2$ are regular expressions then so are $(R_1 \cup R_2)$, $(R_1R_2)$, and $(R_1^*)$. The language denoted by $R$, written $L(R)$, follows the same induction, with union, concatenation, and star of languages taken clause by clause.

$\emptyset$ and $\varepsilon$ denote different languages: the first contains no strings, the second contains the empty string. $L(R^*)$ always contains $\varepsilon$, since concatenating zero strings gives $\varepsilon$. Kleene's theorem, in Lecture 4, proves that a language is regular exactly when some regular expression denotes it, so this notation and the machines of Lecture 3 describe the same class. A language has many expressions denoting it; there is no canonical one.