1. Why regular expressions

What are regular expressions for?

Regular expressions are used whenever a task requires pattern matching:

• search engines
• protein analysis (bioinformatics)
• search and replace in text editors
• text processing utilities such as sed and awk

Many programming languages provide various regular expression capabiltiies. Lexical analysers in compilers also use regular expressions.

Finite representation of languages

Consider the following language:

$$\begin{array}{r}L=\text{all strings of }\alpha \text{ and }\beta \text{ that have two or three occurrences of }\beta ,\\ \text{ the first and second of which are not consecutive}\end{array}$$

Can we describe this infinite language with a finite pattern?

• Strings in $L$ can start with any number (possibly none) of $\alpha$: ${\alpha }^{\ast }$

• Then we have the first $\beta$, it should be alone and followed by at least one $\alpha$: $\beta \alpha$

• Then any number (possibly none) of $\alpha$: ${\alpha }^{\ast }$

• Then comes the second $\beta$: $\beta$

• Then either:

  • No more $\beta$ but can be any number (possible none) of $\alpha$.
  • Or after some (possibly none) $\alpha$, there is a third $\beta$ somewhere, followed by any number (possibly none) $\alpha$.

  This gives us: ${\alpha }^{\ast }\cup {\alpha }^{\ast }\beta {\alpha }^{\ast }$

Combining all of these together gives us:

$${\alpha }^{\ast }\beta \alpha {\alpha }^{\ast }\beta ({\alpha }^{\ast }\cup {\alpha }^{\ast }\beta {\alpha }^{\ast })⇝\underline{\text{ regular expression }}\text{ representing }L$$