Regular Expressions & Languages

Regex syntax, the languages they denote, and Kleene's theorem.

The idea

A regular expression is a notation for describing a language — a set of strings — by assembling it from the smallest languages there are. Where a finite automaton recognizes a language by running on each string, a regular expression describes the whole set at once.

The atoms are $\varnothing$, the language with no strings; $\varepsilon$, the language whose only member is the empty string; and, for each symbol $a$ of the alphabet $\Sigma$, the language $\{a\}$. Three operations combine languages already built. Union $R_1 \cup R_2$ matches whatever either side matches. Concatenation $R_1 R_2$ matches a string of $R_1$ followed by a string of $R_2$, in that order. Star $R^{}$ matches zero or more strings of $R$ run together; taking zero copies leaves the empty string, so $\varepsilon \in L(R^{})$ for every $R$.

A regular expression is any expression assembled from the atoms by these operations, and the set of strings it matches is the language it denotes, written $L(R)$. The expression is notation and $L(R)$ is the set; different expressions can denote the same set.

One theorem connects describing to recognizing.

Theorem (Kleene's theorem).

A language is denoted by some regular expression if and only if it is recognized by some finite automaton.

The two notions reach exactly the same class of languages, the regular ones.

Ways to work on it

• Walkthrough. Union, concatenation, star, and the language a regex denotes.
• Practice. Test string membership in a small regex's language.
• Hardest. Count the strings of a given length that a regex matches, then find the count for every length.

Not sure where to start? Take the ten-question placement test.