Regular Expression

A regular expression (often written as regex) is a syntactic description of a Regular Language over an Alphabet $\sum$.

Regular expressions are built recursively from basic symbols using a small set of operations that correspond to ways of combining languages.

Formally: The class of regular expressions over $\sum$ is defined by:

1. Base cases:
   • $\varnothing$ represents the empty language.
   • $\epsilon$ represents the language $\{\epsilon \}$ containing only the Empty String.
   • For each symbol $a\in \sum$, $a$ represents the language $\{a\}$.
2. Recursive Case
   • If $r_1,r_2$ are regular expressions, then:
     • $r_1+r_2$ (or $r_1\cup r_2$) represents union.
     • $r_1{r}_2$ represents concatenation.
     • $r_1^{\ast }$ represents the Kleene Star (zero or more repetitions).

The language described by a regular expression $r$ is written $L(r)$.

Example

If $\sum =\{a,b\}$, then $(a+b{)}^{\ast }a$ represents all strings over $\{a,b\}$ that end in $a$.