Regular expressions

A regular expression is a text string that lets us describe a set of strings. We can also think of regular expressions as a simple way to describe a finite automaton.

What a regular expression is

In arithmetic we use symbols such as · and + to build an expression like (2 + 3) · 4. Evaluating this expression gives a number. A regular expression is a sequence of characters and a few special symbols, for example a(x ∪ y), and evaluating it gives a (formal) language. The result of the expression (2 + 3) · 4 is the number 20, and the result of the regular expression a(x ∪ y) is the set of two strings “ax” and “ay”.

How would we evaluate the regular expression a(x ∪ y) above? Each letter is really shorthand for a one-element set containing that letter, and the hidden multiplication is the concatenation of strings. We could rewrite the regular expression “in full” like this:

$$\left\{a\right\}\circ (\left\{x\right\}\cup \left\{y\right\})$$

We would then evaluate it as follows: the union {x} ∪ {y} gives us the language {x,y}. Concatenating the languages {a} and {x,y} gives the language {ax, ay}.

Regular expressions are very often used in programming, and most programming languages implement them in some way. For example, they are used to check whether text entered by a user meets certain criteria (such as whether it is a valid email address or a valid date), and to replace text (for example, we might want to replace every URL in a text with a clickable link).

Real implementations of regular expressions are usually more powerful than the regular expressions described here, and they use a slightly different but, above all, more complicated syntax.

Definition of a regular expression

We will define regular expressions over an alphabet Σ. We then say that a regular expression is:

1. a, where a ∈ Σ. That is, a single character of the alphabet is a regular expression.
2. ϵ: the empty string, which in programming is also written as empty quotation marks “”.
3. ∅: a regular expression must also be able to describe the empty language, so the empty language is a regular expression.
4. (R₁ ∪ R₂), where R₁, R₂ are regular expressions.
5. (R₁ ∘ R₂), where R₁, R₂ are regular expressions.
6. (R^∗), where R is a regular expression.

Instead of the symbol ∪ in point 4 we can also use the vertical bar: |. Instead of the symbol ∘ we do not have to use anything. Just as we usually do not write the multiplication symbol, the centred dot ·, we usually do not write the concatenation symbol ∘ either. These regular expressions are therefore identical: a ∘ (b ∪ c) and a(b|c).

What do the individual operators mean?

• ∪ or | denotes the union of languages.
• ∘ denotes the concatenation of languages.
• ^∗ denotes the Kleene closure of a language.

Examples:

• a denotes the simple language {a}.
• a|b denotes the language consisting of the two strings {a, b}.
• a ∘ b denotes the language {ab}.
• a(b|c)d denotes the language {abd, acd}.
• a(b^∗) denotes the language of all strings that start with the letter “a” followed by any number of letters “b”.
• (ab)^∗ denotes the language of all strings {ϵ, ab, abab, ababab, …}.
• 0^∗10^∗ denotes the language of all binary strings that contain exactly one 1. (Notice that it would be more precise to write this expression as (0^∗)1(0^∗), but when the notation is readable without them, we can leave out the brackets.)
• Σ^∗1Σ^∗ denotes the language of all strings containing at least one 1.
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ denotes the language of all positive integers.

Next we will show the equivalence between regular expressions and finite automata. Here, for every regular expression that evaluates to a language R, there is a finite automaton A such that L(A) = R, and vice versa.

Sources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools