Regular Expressions

Regular expressions are a convenient notation for representing strings that match simple text patterns. The expression $a^*ac^*b^*$ illustrates two of the four regular expression operations, namely concatenation (via juxtaposition) and Kleene star. The others appear in the following recursive definition.

Formal definition

1. These are regular expressions:

   a) $\phi$, representing the empty language/set, $\{ \}$

   b) $\lambda$, representing the one-string language/set, $\{\lambda\}$

   c) $c$, for each character, $c$ in the alphabet $\Sigma$, representing the language/set $\{c\}$

2. For regular expressions $r, r_1, r_2$, the following are also regular expressions:

   a) $r_1 + r_2$ (union)

   b) $r_1r_2$ (concatenation)

   c) $r^*$ (Kleene star)

   d) $(r)$ (grouping)

Note: Some authors (and most programming environments) use the notation $r_1 \mid r_2$ for union.

Each regular expression represents a language, which is the set of all strings matching its pattern. Formally, we denote the language associated with a regular expression, $r$, as $L(r)$, so $L(\phi)=\{ \}$, $L(\lambda)=\{\lambda\}$, and $L(c)=\{c\}$ for each symbol $c$ from the alphabet in use. The following expressions also hold:

• $L(r_1+r_2)=L(r_1)\cup L(r_2)$
• $L(r_1r_2)=L(r_1)L(r_2)$

...