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$ ...