Submitted to Chicago Journal of Theoretical Computer Science, August 2000.

A SIMPLE UNIVERSAL PATTERN-MATCHING AUTOMATON

DANIEL J. BERNSTEIN

Abstract. Consider an infinite non-deterministic automaton with one state p for each regular expression p; transitions q →^{c} qS whenever S is a character set containing c; and null transitions q ⇒ q\overline{r} , q\overline{r}r ⇒ q\overline{r} , qr ⇒ q(r′ ∪ r) , and qr′ ⇒ q(r′ ∪ r) . If this automaton starts at the empty regular expression, then p recognizes exactly the language defined by p, for every p. The subautomaton affecting p has at most 1 + len p states.

1. Introduction

This paper presents a nondeterministic infinite automaton that recognizes all regular expressions simultaneously. A portion of the automaton is shown in Figure 1 below.

The automaton has one state p for each regular expression p, and no other states. The language recognized by p is exactly the language defined by p. The subautomaton affecting p has at most 1 + len p states. Here len p is the number of non-parenthesis symbols in p; for example, the length of \overline{?}\overline{xy}xz is 7, and the length of ((xy ∪ z)z) ∪ yyy is 9.

Is it surprising that such an automaton exists? Of course not. It is well known that, for each p, there is a nondeterministic automaton recognizing p with at most 1 + len p states. One can mechanically assign to each state a corresponding regular expression, and finally merge the automata for all p into a single infinite automaton that behaves as described above.

What is surprising about the automaton in this paper is that its definition is extremely short. There is one transition q →^{c} qC for each regular expression q, character c, and character set C containing c. There are null transitions q ⇒ q\overline{r} , q\overline{r}r ⇒ q\overline{r} , qr ⇒ q(r′ ∪ r) , and qr′ ⇒ q(r′ ∪ r) , for all regular expressions q, r, r′. The automaton begins at () where () is the empty pattern. That’s it.

These transitions are visibly correct, in the sense that any string recognized by p is in the language defined by p. It is not as easy to prove that these transitions are adequate, in the sense that any string in the language defined by p is recognized by p . See Theorem 4.1 and Theorem 4.2. It also takes some work to prove that the subautomaton affecting p has at most 1 + len p states. See Theorem 7.2. These proofs occupy the remaining sections of this paper.

Date: 20000806.

1991 Mathematics Subject Classification. Primary 68Q45.

Key words and phrases. Regular expressions, nondeterministic infinite automata.

The author was supported by the National Science Foundation under grant DMS–9600083.

()

[figure] [figure] [figure]

          x

[figure]

           x

                       y

[figure]

                    xy

                                      z

[figure]

                               xyz

                                                      z

[figure]

                                          xyzz

                                                                          y

[figure]

                                                          xyzzy

[figure]

           \overline{?} [figure]

                        z

[figure]

                     y

[figure]

                  x

[figure]

                    \overline{?}\overline{xy} x [figure] \overline{?}\overline{xy}x z [figure]

                                               y

[figure]

                                          \overline{?}\overline{xy}xz

[figure]

                                                      \overline{?}\overline{xy}xz ∪ xyzzy

           \overline{?}?

[figure]

                              \overline{?}\overline{xy}xy

[figure]

[figure]

Figure 1. A portion of the automaton over the alphabet {x, y, z}.

Notation and terminology. The string (c_{1}, …, c_{n}) is abbreviated as “c_{1} … c_{n}”. For example, “x”, “xyz”, and “xyzzy” are strings over the alphabet {x, y, z}.

A constant is a set of single-character strings. The set of all single-character strings is denoted ?. At the risk of confusion, I abbreviate the constant {“c”} as c for each character c.

A pattern algebra is a set with an associative binary operation “composition” written p, q ↦ pq, a neutral element for composition written (), a unary operation “closure” written p ↦ \overline{p}, and a binary operation “union” written p, q ↦ p ∪ q. For example, the set of regular languages is a pattern algebra with composition L, M ↦ LM = {st : s ∈ L, t ∈ M}; neutral element () = {“”}; union equalling the usual set union; and closure L ↦ \overline{L} = L^{0} ∪ L^{1} ∪ · · ·.

A pattern is an element of the free pattern algebra on the set of constants. In other words, a pattern is a formula built up from constants via union, closure, and composition, modulo redundant parentheses and the associativity of composition. Every pattern falls into one of the four forms (), qC, q\overline{r}, or q(r′ ∪ r); here q, r′, and r are patterns, and C is a constant.

I write s ∈ p, and say p matches s, to mean that s is contained in the language defined by p. Here p is a pattern and s is a string.

Historical notes. Thompson in [1] constructed an automaton recognizing p with O(len p) states. See [2] for a coherent survey of subsequent constructions. My construction is simpler than any of the constructions in [2].

I wrote down my automaton in June 1991, and distributed an implementation in a posting to alt.sources in January 1992. I was not familiar with the literature; the construction seemed so obvious that I assumed it was what everyone had always done. In April 1994, after reading a preliminary version of the taxonomy in [2], I announced my automaton in a posting to comp.theory.

2. Pattern implication

The relation “p′⇒p” is the transitive closure of the basic implications “q⇒q\overline{r}”, “q\overline{r}r ⇒q\overline{r}”, “qr ⇒q(r′ ∪r)”, and “qr′ ⇒q(r′ ∪r)”. In other words, p′ ⇒p if and only if there is a chain p′ = p_{0} ⇒ p_{1} ⇒ ⋯ ⇒ p_{n} = p of basic implications. In particular p ⇒ p.

For example, () ⇒ \overline{?}, and \overline{?} ⇒ \overline{?}\overline{xy}, so () ⇒ \overline{?}\overline{xy}.

Theorem 2.1. If p′ ⇒ p and s ∈ p′ then s ∈ p.

Proof. It suffices to check the basic implications: if s ∈ q or s ∈ q\overline{r}r then s ∈ q\overline{r}; and if s ∈ qr or s ∈ qr′ then s ∈ q(r′ ∪ r).

Theorem 2.2. If p′ ⇒ p then p′′p′ ⇒ p′′p.

Proof. This is a purely formal consequence of the definition: p′′q\overline{r}r ⇒ p′′q\overline{r}, p′′q ⇒ p′′q\overline{r}, p′′qr⇒p′′q(r′∪r), and p′′qr′⇒p′′q(r′∪r), so given a chain of basic implications we may prepend p′′ to each term.

3. The impl function

Define recursively

impl p = \begin{cases}\{p\} & if p = () or p = qC, \\ impl qr′ ∪ impl qr & if p = q(r′ ∪ r), \\ impl q ∪ \{q\overline{r}y : y ∈ impl r, y ≠ ()\} & if p = q\overline{r}. \end{cases}

For example, impl \overline{?}\overline{xy} = \{(), \overline{?}?, \overline{?}\overline{xy}xy\}.

Theorem 3.1. If x ∈ impl p then x ⇒ p.

Proof. Induct on len p. First, if p = () or p = qC then x = p so x ⇒ p.

Second, say p = q(r′ ∪ r). If x ∈ impl qr′ then by induction x ⇒ qr′ ⇒ p. If x ∈ impl qr then by induction x ⇒ qr ⇒ p.

Third, say p = q\overline{r}. If x ∈ impl q then by induction x ⇒ q ⇒ p. If x = q\overline{r}y, with y ∈ impl r, then by induction y ⇒ r, so x = q\overline{r}y ⇒ q\overline{r}r ⇒ p by Theorem 2.2.

Theorem 3.2. If x ∈ impl p then x is empty or ends with a constant.

Proof. Induct on len p. First, if p = () or p = qC then x = p.

Second, if p = q(r′ ∪ r) then x ∈ impl qr′ or x ∈ impl qr; by induction x is empty or ends with a constant.

Third, say p = q\overline{r}. If x ∈ impl q then by induction x is empty or ends with a constant. If x = q\overline{r}y, with () ≠ y ∈ impl r, then by induction y ends with a constant, so x does too.

Theorem 3.3. If s ∈ p then s ∈ x for some x ∈ impl p.

Proof. Induct on len p. First, if p = () or p = qC then p ∈ impl p so there is nothing to prove.

Second, if p = q(r′ ∪ r) then s ∈ qr′ or s ∈ qr. So by induction s ∈ x where x ∈ impl qr′ or x ∈ impl qr. Either way x ∈ impl p.

Third, if p = q\overline{r} then s = t′t with t′ ∈ q, t ∈ \overline{r}. If t = “” then s = t′ ∈ q so by induction there is an x ∈ impl q with s ∈ x; and x ∈ impl p. If t ≠ “” we may write t = uv where u ∈ \overline{r} and v ∈ r, v ≠ “”. By induction there is a y ∈ impl r with v ∈ y; since v is nonempty we cannot have y = (). Thus q\overline{r}y ∈ impl p, and s = t′uv ∈ q\overline{r}y as desired.

4. Consequences of impl

Theorem 4.1 says that my automaton works for the empty string. Theorem 4.2 says that, if my automaton works for a string t, then it also works for t plus any character.

Theorem 4.1. “” ∈ p if and only if () ⇒ p.

Proof. Say () ⇒ p. Certainly “” ∈ (); by Theorem 2.1, “” ∈ p.

Conversely, say “” ∈ p. By Theorem 3.3, “” ∈ x for some x ∈ impl p. Since “” ∈ x, x cannot end with a constant; thus, by Theorem 3.2, x = (). By Theorem 3.1, () = x ⇒ p.

Theorem 4.2. t“c” ∈ p if and only if there exist q and C such that t ∈ q, “c” ∈ C, and qC ⇒ p.

Proof. If t ∈ q and “c” ∈ C then t“c” ∈ qC; if also qC ⇒ p then t“c” ∈ p by Theorem 2.1.

Conversely, say t“c” ∈ p. By Theorem 3.3, t“c” ∈ x for some x ∈ impl p. Since t“c” ≠ “”, x cannot be empty; thus, by Theorem 3.2, x ends with a constant. Write x = qC. Then t ∈ q and “c” ∈ C. Finally qC = x ⇒ p by Theorem 3.1.

5. Left subpatterns

The relation “p′ is a left subpattern of p” is the transitive closure of the relations “q is a left subpattern of qC”, “q\overline{r}r is a left subpattern of q\overline{r}”, “q is a left subpattern of q\overline{r}”, “qr is a left subpattern of q(r′∪r)”, and “qr′ is a left subpattern of q(r′∪r)”.

In other words, p′ is a left subpattern of p if and only if p′ affects p in my automaton. Therefore, if s ∈ p, then any prefix s′ of s satisfies s′ ∈ p′ for some left subpattern p′ of p.

Example: \overline{?}? is a left subpattern of \overline{?}, which is a left subpattern of \overline{?}\overline{xy}, which is a left subpattern of \overline{?}\overline{xy}x, which is a left subpattern of \overline{?}\overline{xy}xz. So \overline{?}? is a left subpattern of \overline{?}\overline{xy}xz.

6. The left function

Define left_{0} p = p. Define left_{n+1} p for each n as follows:

left_{n+1} p = \begin{cases}undefined & if p = () \\ left_{n} q & if p = qC \\ left_{n} q\overline{r}r & if p = q\overline{r}, n < len r \\ left_{n−len r} q & if p = q\overline{r}, n ≥ len r \\ left_{n} qr & if p = q(r′ ∪ r), n < len r \\ left_{n−len r} qr′ & if p = q(r′ ∪ r), n ≥ len r. \end{cases}

For example, the values of left_{n} \overline{?}\overline{xy}xz, as n increases from 0 through 7, are \overline{?}\overline{xy}xz, \overline{?}\overline{xy}x, \overline{?}\overline{xy}, \overline{?}\overline{xy}xy, \overline{?}\overline{xy}x, \overline{?}, \overline{?}?, and (). For n > 7, left_{n} \overline{?}\overline{xy}xz is undefined.

The reader may enjoy verifying certain facts not needed in this paper: left_{len p} p = (); if n < len p then left_{n} p is defined and nonempty; if n ≤ len p then left_{n} p′p = p′ left_{n} p; if left_{n} p is defined then it is a left subpattern of p.

Theorem 6.1. If n > len p then left_{n} p is undefined.

Proof. Induct on n. Note that n > 0.

If p = () then left_{n} p is undefined. If p = qC then n > n − 1 > len q so left_{n−1} q is undefined by induction; so left_{n} p = left_{n−1} q is undefined. If p = q\overline{r} then n > n − 1 − len r > len q so left_{n−1−len r} q is undefined by induction; so left_{n} p = left_{n−1−len r} q is undefined. If p = q(r′ ∪ r) then n > n − 1 − len r > len qr′ so left_{n−1−len r} qr′ is undefined by induction; so left_{n} p = left_{n−1−len r} qr′ is undefined.

Theorem 6.2. left_{n} p′p = left_{n−len p} p′ if n ≥ len p.

Proof. Induct on n.

If p = () then len p = 0 and p′p = p′ as desired. If p = qC then n > n − 1 ≥ len q so

left_{n} p′p = left_{n−1} p′q = left_{n−1−len q} p′ = left_{n−len p} p′

by induction. If p = q\overline{r} then n > n − 1 − len r ≥ len q so

left_{n} p′p = left_{n−1−len r} p′q = left_{n−1−len r−len q} p′ = left_{n−len p} p′

by induction. If p = q(r′ ∪ r) then n > n − 1 − len r ≥ len qr′ so

left_{n} p′p = left_{n−1−len r} p′qr′ = left_{n−1−len r−len qr′} p′ = left_{n−len p} p′

by induction.

7. The J function

Theorem 7.2 states that all left subpatterns of p are values of left_{n} p for n ∈ {0, 1, …, len p}. Thus the number of states affecting p in my automaton is at most 1 + len p.

Define J(p, m, 0) = m. For each n define J(p, m, n + 1) =

undefined  if p = ()
J(q, m, n) + 1  if p = qC
J(q\overline{r}r, m, n) + 1  if p = q\overline{r}, n < len r, J(q\overline{r}r, m, n) < len r
J(q\overline{r}r, m, n) − len r  if p = q\overline{r}, n < len r, J(q\overline{r}r, m, n) ≥ len r
J(q, m, n − len r) + len r + 1 if p = q\overline{r}, n ≥ len r
J(qr, m, n) + 1  if p = q(r′ ∪ r), n < len r, J(qr, m, n) < len r
J(qr, m, n) + len r′ + 1  if p = q(r′ ∪ r), n < len r, J(qr, m, n) ≥ len r
J(qr′, m, n − len r) + len r + 1 if p = q(r′ ∪ r), n ≥ len r.

Theorem 7.1. left_{m} left_{n} p = left_{J(p,m,n)} p if left_{n} p is defined.

Proof. If n = 0 then J(p, m, n) = m and left_{n} p = p; thus left_{J(p,m,n)} p = left_{m} p = left_{m} left_{n} p.

Now induct on n. Assume left_{n+1} p is defined. Note that n + 1 ≤ len p by Theorem 6.1, so p ≠ (). I will show that left_{m} left_{n+1} p = left_{J(p,m,n+1)} p.

1. Say p = qC. Write j = J(q, m, n). Then

left_{m} left_{n+1} p = left_{m} left_{n} q = left_{j} q = left_{j+1} p.

2. Say p = q\overline{r} and n < len r. Write j = J(q\overline{r}r, m, n). Observe that

left_{m} left_{n+1} p = left_{m} left_{n} q\overline{r}r = left_{j} q\overline{r}r.

If j < len r then left_{j} q\overline{r}r = left_{j+1} p; else left_{j} q\overline{r}r = left_{j−len r} q\overline{r} = left_{j−len r} p. 3. Say p = q\overline{r} and n ≥ len r. Write j = J(q, m, n − len r). Then

left_{m} left_{n+1} p = left_{m} left_{n−len r} q = left_{j} q = left_{j+len r+1} p.

4. Say p = q(r′ ∪ r) and n < len r. Write j = J(qr, m, n). Observe that

left_{m} left_{n+1} p = left_{m} left_{n} qr = left_{j} qr.

If j < len r then left_{j} qr = left_{j+1} p; otherwise

left_{j} qr = left_{j−len r} q = left_{j−len r+len r′} qr′ = left_{j+len r′+1} p.

5. Say p = q(r′ ∪ r) and n ≥ len r. Write j = J(qr′, m, n − len r). Then

left_{m} left_{n+1} p = left_{m} left_{n−len r} qr′ = left_{j} qr′ = left_{j+len r+1} p.

Theorem 7.2. If p′ is a left subpattern of p then p′ = left_{n} p for some n.

Proof. If p = qC then q = left_{1} p.

If p = q\overline{r} then q = left_{len r+1} p. Furthermore q\overline{r}r = left_{1} p if r ≠ (); q\overline{r}r = left_{0} p if r = ().

If p = q(r′ ∪ r) then qr′ = left_{len r+1} p. Furthermore qr = left_{1} p if r ≠ (). If r = () then qr = q = left_{len r′} qr′ = left_{len r′+1} p by Theorem 6.2.

Finally, by Theorem 7.1, the relation “p′ is left_{n} p for some n” is transitive.

References

[1] Ken Thompson, Regular expression search algorithm, Communications of the ACM 11 (1968), 419–422.

[2] Bruce W. Watson, Taxonomies and toolkits of regular language algorithms, Ph.D. thesis, Eindhoven University of Technology, 1995.

Department of Mathematics, Statistics, and Computer Science, The University of Illinois at Chicago, Chicago, IL 60607–7045

E-mail address: djb@pobox.com