Regular Expressions

Describing regular languages and converting between representations

From machines to descriptions

Finite automata describe regular languages operationally: they show how a machine recognizes strings. Regular expressions describe the same languages declaratively: they specify what form accepted strings have.

Regular expressions provide a compact—but not always immediately readable—language for describing patterns.

A regular expression is:

a concise description of a language;
a textual representation that can be entered into a program; and
a combination of alphabet symbols and a small collection of operators.

In formal language theory, the fundamental operators are:

union, written \(R_1\cup R_2\) or sometimes R1 + R2;
concatenation, written \(R_1R_2\); and
Kleene star, written \(R^*\).

Classical regular expressions do not require primitive intersection or complement operators. Those operations preserve regularity, but they can be expressed using automata and other constructions.

A motivating example: email-like strings

Suppose we want to describe strings formatted approximately like an email address. A simplified practical pattern might be written as:

[A-Za-z0-9]+@[A-Za-z0-9]+(\.[A-Za-z0-9]+)*\.(edu|com|net|gov)

This illustrates how regular-expression syntax can express:

character classes, such as [A-Za-z0-9];
one or more repetitions, written + in many programming libraries;
literal punctuation, such as \.;
grouping with parentheses; and
alternatives, written with |.

This pattern is useful for illustration, but it is not a complete implementation of the modern email-address specification.

Note

Programming-language regex libraries usually extend the mathematical definition with convenient syntax. Context determines whether + means union or one-or-more repetition. In these notes, \(\cup\) denotes mathematical union whenever ambiguity is possible.

Formal definition

Regular expressions over an alphabet \(\Sigma\) are defined recursively.

Base expressions

Regular expression	Language described
\(a\), for \(a\in\Sigma\)	\(\{a\}\)
\(\varepsilon\)	\(\{\varepsilon\}\)
\(\varnothing\)	\(\varnothing\)

It is important to distinguish \(\varepsilon\) from \(\varnothing\):

\(\varepsilon\) is a string of length zero;
\(\{\varepsilon\}\) is a language containing that one string; and
\(\varnothing\) is a language containing no strings.

Recursive expressions

If \(R_1\) and \(R_2\) are regular expressions, then the following are also regular expressions:

Expression	Language described
\(R_1\cup R_2\)	\(L(R_1)\cup L(R_2)\)
\(R_1R_2\)	\(\{xy:x\in L(R_1),\ y\in L(R_2)\}\)
\(R_1^*\)	\(\displaystyle\bigcup_{n\ge 0}L(R_1)^n\)

Here \(L^0=\{\varepsilon\}\), and \(L^n\) contains all concatenations of \(n\) strings from \(L\). Consequently, \(R^*\) always describes a language containing \(\varepsilon\).

Nothing else is a regular expression unless it can be built using these rules.

Reading regular expressions

Assume \(\Sigma=\{0,1\}\).

\(0^\cup 1^\)

All strings consisting entirely of 0s or entirely of 1s:

\[ \{\varepsilon,0,00,000,\ldots,1,11,111,\ldots\}. \]

It does not include strings mixing the two symbols.

\(0^1^\)

Any number of 0s followed by any number of 1s. Examples include

\[ \varepsilon,0,1,000,111,00111. \]

Once a 1 appears, no later 0 is permitted.

\(00^11^\)

At least one 0, followed by at least one 1. Using the common shorthand \(R^+=RR^*\) for one or more repetitions, this is

\[ 0^+1^+. \]

\((0\cup1)^*\)

Every binary string, including \(\varepsilon\):

\[ (0\cup1)^*=\Sigma^*. \]

\(10^1\) versus \(1(0\cup1)^1\)

\(10^*1\) describes strings that begin and end with 1 and contain only 0s between them.
\(1(0\cup1)^*1\) describes binary strings that begin and end with 1 and may contain anything between them.

Neither expression accepts the one-character string 1. If the intended language includes all strings that begin and end with 1, including 1 itself, use

\[ 1\cup1(0\cup1)^*1. \]

Design strategy

When constructing a regular expression, separate the language into required pieces:

What may appear before the important pattern?
What symbols or substrings are required?
What may appear between required parts?
What may appear afterward?
Must \(\varepsilon\) be included?

For example, binary strings containing the substring 110 can be described by

\[ (0\cup1)^*110(0\cup1)^*. \]

The two starred expressions permit arbitrary binary prefixes and suffixes.

Practice

Construct regular expressions for the following binary languages:

strings containing at least two 0s;
strings containing the substring 110;
strings whose symbols in every even-numbered position are 0;
strings of even length;
strings whose final two symbols are equal.

Then answer:

What is wrong with using \(1^*01^*01^*\) for strings containing at least two 0s?
What is wrong with using \(((0\cup1)^*0)^*\) for strings whose even-numbered symbols are 0?
What is the shortest string not described by \(1^*(01)^*0^*\)?
Do \(111^*\) and \((11\cup111)^*\) describe the same language?

Hints

In Question 1, arbitrary symbols must be permitted before, between, and after the required 0s.
In Question 3, group the string into two-symbol blocks and handle a possible final odd-position symbol.
To disprove equivalence in Question 9, look for a short string belonging to only one language.

How powerful are regular expressions?

Two questions connect regular expressions to finite automata:

Given any regular expression, is there an NFA recognizing the same language?
Given any finite automaton, is there a regular expression describing the same language?

The answer to both is yes.

Theorem. A language is regular if and only if some regular expression describes it.

Equivalently,

\[ \mathcal{L}(\mathrm{RE})=\mathcal{L}(\mathrm{NFA})=\mathcal{L}(\mathrm{DFA}). \]

We prove equality by proving both containments.

From a regular expression to an NFA

We prove

\[ \mathcal{L}(\mathrm{RE})\subseteq\mathcal{L}(\mathrm{NFA}) \]

by structural induction on the recursive definition of regular expressions.

Base cases

It is straightforward to construct small NFAs for:

\(a\), which accepts only the one-character string \(a\);
\(\varepsilon\), which accepts only the empty string; and
\(\varnothing\), which accepts nothing.

Inductive hypothesis

Assume NFAs \(N_1\) and \(N_2\) recognize \(L(R_1)\) and \(L(R_2)\).

Union

To recognize \(R_1\cup R_2\), create a new start state with \(\varepsilon\)-transitions to the start states of \(N_1\) and \(N_2\). Retain the accepting states of both machines.

This is the same construction used to prove that the regular languages are closed under union.

Concatenation

To recognize \(R_1R_2\), add \(\varepsilon\)-transitions from the accepting states of \(N_1\) to the start state of \(N_2\). The resulting machine accepts a prefix using \(N_1\) and the remaining suffix using \(N_2\).

Kleene star

To recognize \(R_1^*\), add a new accepting start state. Connect it to the old start with an \(\varepsilon\)-transition, and connect the old accepting states back to the old start. This permits zero or more repetitions.

Because every regular expression is built from the base cases using these three operations, every regular expression has an equivalent NFA.

Construction exercise

Use the inductive construction to build an NFA for

\[ (a\cup b)^*b. \]

Before simplifying, construct the machine directly from the expression’s recursive structure.

From a finite automaton to a regular expression

We now prove

\[ \mathcal{L}(\mathrm{FA})\subseteq\mathcal{L}(\mathrm{RE}). \]

Guessing a regular expression by inspecting a complicated automaton is unreliable. Instead, we use a systematic state-elimination procedure.

Even a small DFA can make its complete regular expression difficult to guess.

Generalized NFAs

During state elimination, transitions are labeled with regular expressions rather than individual symbols. The resulting intermediate machine is called a generalized NFA (GNFA).

Preparation

Add a new start state with an \(\varepsilon\)-transition to the original start state.
Add one new accepting state.
Add an \(\varepsilon\)-transition from every original accepting state to the new accepting state.
Ensure there is one regular-expression label between each ordered pair of states:
- combine multiple labels using union;
- use \(\varnothing\) when no transition exists.

The new start state has no incoming transitions, and the new accepting state has no outgoing transitions.

Eliminating a state

Suppose we eliminate state \(X\). For every remaining pair of states \(A\) and \(B\), replace the label from \(A\) to \(B\) with

\[ R'_{AB} = R_{AB}\cup R_{AX}(R_{XX})^*R_{XB}. \]

State elimination preserves paths that previously passed through the removed state.

This formula accounts for two ways to travel from \(A\) to \(B\):

go directly from \(A\) to \(B\) using \(R_{AB}\); or
enter \(X\), loop at \(X\) zero or more times, and then leave \(X\).

Useful simplifications include:

\[ R\cup\varnothing=R, \qquad R\varnothing=\varnothing R=\varnothing, \qquad \varnothing^*=\varepsilon, \qquad R\varepsilon=\varepsilon R=R. \]

Continue eliminating states until only the new start and accepting states remain. The label between them is a regular expression for the original automaton’s language.

State-elimination example 1

First, add new start and accepting states to the two-state automaton.

The original DFA and its corresponding GNFA with new start and accepting states.

Eliminate \(s_1\)

The new label from start to \(s_2\) is

\[ \varnothing\cup\varepsilon 1^*0=1^*0. \]

The updated loop on \(s_2\) is

\[ 1\cup01^*0. \]

The GNFA after eliminating state \(s_1\).

Eliminate \(s_2\)

The final start-to-accept label becomes

\[ \varnothing\cup1^*0(1\cup01^*0)^*\varepsilon, \]

which simplifies to

\[ 1^*0(1\cup01^*0)^*. \]

This is a regular expression describing the original DFA’s language.

State-elimination example 2

Begin by adding a new start state and new accepting state.

A second automaton prepared for state elimination.

After eliminating state \(1\):

\[ R_{\text{start},2} = \varnothing\cup\varepsilon a^*b =a^*b, \]

\[ R_{2,2}=a\cup b, \]

and the edge from state \(2\) to end remains \(\varepsilon\).

Eliminating state \(2\) produces

\[ a^*b(a\cup b)^*. \]

This expression describes strings containing at least one b: any number of as may appear before the first selected b, followed by any binary suffix.

Why state elimination proves the theorem

Each elimination step preserves the set of strings labeling paths from the new start state to the new accepting state. Because the process removes one state at a time, it must eventually leave a single regular-expression label describing exactly the original machine’s language.

We have now established both directions: