Regular expressions and closure properties

Finite automata describe regular languages by machines. Regular expressions describe the same languages by formulas built from three operations: union, concatenation and star. You use regular expressions every day in editors, shells and programming languages, and CMPUT-415 compiled them into scanners. This lesson proves that expressions and automata have exactly the same power, a result known as Kleene's theorem, and then uses the two descriptions together to show that regular languages are closed under a long list of operations. Closure properties are the main tool for showing that a language is regular without building an automaton for it directly, and, combined with the pumping lemma of lesson 4, for showing that a language is not regular.

Regular expressions

Regular expressions over an alphabet \(\Sigma\) are defined inductively. The base cases are \(\emptyset\), which denotes the empty language; \(\varepsilon\), which denotes \(\{\varepsilon\}\); and each symbol \(a \in \Sigma\), which denotes \(\{a\}\). If R and S are regular expressions, so are \((R \cup S)\), denoting \(L(R) \cup L(S)\); \((RS)\), denoting the concatenation \(L(R)L(S)\); and \(R^*\), denoting \(L(R)^*\). Parentheses may be dropped using the precedence star, then concatenation, then union, so \(ab^* \cup c\) means \((a(b^*)) \cup c\). Practical regex syntaxes write union as a vertical bar and add conveniences such as \(R^+ = RR^*\), optional parts, character classes and counted repetition, all of which can be expanded into the three basic operations.

Some examples over \(\{0, 1\}\): \(\Sigma^* 1 \Sigma^*\) denotes the strings containing at least one 1; \((\Sigma\Sigma)^*\) the strings of even length; \(0^* 1 0^*\) the strings with exactly one 1; \((0 \cup 10)^*(\varepsilon \cup 1)\) the strings with no two consecutive 1s. Writing an expression for a language is like writing a small program: break the language into pieces, describe each, and combine. The challenge is precision. The expression for 'no two consecutive 1s' must allow a single 1 at the very end, which is the role of the final \((\varepsilon \cup 1)\).

Many practical regex engines add backreferences, which let a pattern refer to text matched earlier, as in a pattern for a repeated word. Backreferences take the notation outside regular languages: with them one can describe \(\{ww : w \in \Sigma^*\}\), which is not regular, and matching becomes NP-hard in general. The theory in this course concerns true regular expressions without backreferences. Engines that restrict themselves to that fragment can guarantee matching in time linear in the input, which is why they are preferred for untrusted patterns or inputs, where backtracking engines can be driven into exponential time.

Kleene's theorem

Theorem (Kleene, 1956). A language is regular if and only if some regular expression describes it. The proof has two directions, illustrated by the equivalence triangle in the figure. From expression to automaton, we build an NFA by induction on the structure of the expression: small NFAs for the base cases, and constructions for union, concatenation and star that glue NFAs together with \(\varepsilon\)-transitions. This is Thompson's construction from CMPUT-415, and its correctness is a routine induction: each glued machine accepts exactly the union, concatenation or star of its parts' languages. From automaton to expression is the less familiar direction, and we prove it by state elimination.

State elimination works on a generalized NFA (GNFA), whose transitions are labelled by regular expressions rather than single symbols. Start from a DFA, add a new start state with an \(\varepsilon\)-edge to the old start, and a new accepting state with \(\varepsilon\)-edges from every old accepting state. Then remove the original states one at a time. To remove state k, for every pair of remaining states i and j, replace the label on the edge from i to j by \(R_{ij} \cup R_{ik}R_{kk}^*R_{kj}\): either go directly, or go to k, loop there any number of times, and leave to j. Each removal preserves the language, because every path through k is accounted for by the new label. When only the new start and new accepting states remain, the label between them is a regular expression for the language.

The program below performs state elimination on the divisible-by-3 DFA from lesson 2, removing \(q_2\), then \(q_1\), then \(q_0\), and checks the resulting expression with Python's re module against arithmetic on every binary string up to length 10. Here, with redundant parentheses removed, the result is the compact expression \((0 \cup 1(01^*0)^*1)^*\), which can even be read directly: a 0 keeps the remainder at 0, and a block \(1(01^*0)^*1\) leaves remainder 0, passes through remainders 1 and 2 in between, and returns. Such tidy results are the exception. In general state elimination can produce expressions exponentially longer than the automaton, and the order of elimination affects the size considerably. Finding the shortest expression for a language is computationally hard, so tools that need readable expressions use heuristics.

# State elimination: convert the divisible-by-3 DFA into a regular expression,
# then check the expression against the DFA on every binary string up to length 10.
import re
from itertools import product

def union(a, b):
    if a is None: return b
    if b is None: return a
    return a if a == b else f"{a}|{b}"
def cat(a, b):
    if a is None or b is None: return None
    wrap = lambda x: f"({x})" if "|" in x else x
    return wrap(a) + wrap(b)
def star(a):
    if a is None or a == "": return ""
    return f"({a})*"

# GNFA edges R[(i, j)] = regex; S is a new start, A a new accept state
R = {}
def add(i, j, r): R[(i, j)] = union(R.get((i, j)), r)
delta = {(r, b): (2 * r + int(b)) % 3 for r in range(3) for b in "01"}
for (r, b), t in delta.items(): add(r, t, b)
add("S", 0, ""); add(0, "A", "")            # epsilon edges written as the empty regex

for k in [2, 1, 0]:                          # rip out q2, then q1, then q0
    loop = star(R.get((k, k)))
    ins = [i for (i, j) in list(R) if j == k and i != k]
    outs = [j for (i, j) in list(R) if i == k and j != k]
    for i in ins:
        for j in outs:
            add(i, j, cat(cat(R[(i, k)], loop), R[(k, j)]))
    R = {e: r for e, r in R.items() if k not in e}
    print(f"after removing q{k}: {len(R)} edge(s)")
regex = R[("S", "A")]
print("regex:", regex)
print("length:", len(regex), "characters")

pat = re.compile(regex)
bad = 0
for n in range(1, 11):
    for t in product("01", repeat=n):
        w = "".join(t)
        bad += bool(pat.fullmatch(w)) != (int(w, 2) % 3 == 0)
print("disagreements with arithmetic on 2046 strings:", bad)

after removing q2: 6 edge(s)
after removing q1: 3 edge(s)
after removing q0: 1 edge(s)
regex: (((0|1(0(1)*0)*1)*))
length: 20 characters
disagreements with arithmetic on 2046 strings: 0

Closure properties

A class of languages is closed under an operation if applying the operation to languages in the class always gives a language in the class. Regular languages are closed under union, concatenation and star directly from the definition of regular expressions, or by the NFA constructions in Thompson's method. They are closed under complement because a DFA can be complemented by swapping accepting and non-accepting states; this is where determinism matters, and why we convert an NFA to a DFA first. Closure under intersection then follows from De Morgan's law, \(A \cap B = \overline{\overline{A} \cup \overline{B}}\), but a direct construction is more useful.

The product construction runs two DFAs in parallel. Given \(M_1 = (Q_1, \Sigma, \delta_1, s_1, F_1)\) and \(M_2 = (Q_2, \Sigma, \delta_2, s_2, F_2)\), build \(M\) with states \(Q_1 \times Q_2\), start state \((s_1, s_2)\), and transitions \(\delta((p, q), a) = (\delta_1(p, a), \delta_2(q, a))\). An induction on string length shows that \(\hat\delta((s_1, s_2), w) = (\hat\delta_1(s_1, w), \hat\delta_2(s_2, w))\). Choosing accepting states \(F_1 \times F_2\) gives the intersection; choosing pairs where either component accepts gives the union; choosing pairs where the first accepts and the second does not gives the difference \(L_1 \setminus L_2\). One construction, with different accepting sets, handles every Boolean combination.

# Product construction: a DFA for the intersection of two regular languages.
# A = even number of 0s (states E, O);  B = ends in 1 (states n, y).
from itertools import product
A = {"start": "E", "acc": {"E"}, "d": {("E", "0"): "O", ("O", "0"): "E", ("E", "1"): "E", ("O", "1"): "O"}}
B = {"start": "n", "acc": {"y"}, "d": {(q, "0"): "n" for q in "ny"} | {(q, "1"): "y" for q in "ny"}}

def product_dfa(M1, M2, mode):
    states = [(p, q) for p in ("E", "O") for q in ("n", "y")]
    d = {((p, q), c): (M1["d"][(p, c)], M2["d"][(q, c)]) for (p, q) in states for c in "01"}
    test = {"and": lambda a, b: a and b, "or": lambda a, b: a or b, "minus": lambda a, b: a and not b}[mode]
    acc = {(p, q) for (p, q) in states if test(p in M1["acc"], q in M2["acc"])}
    return {"start": (M1["start"], M2["start"]), "acc": acc, "d": d}

def run(M, w):
    q = M["start"]
    for c in w: q = M["d"][(q, c)]
    return q in M["acc"]

P = product_dfa(A, B, "and")
print("states:", sorted(set(q for q, _ in P["d"])))
print("accepting:", sorted(P["acc"]))
for w in ["1", "01", "001", "0011", "0101", "100"]:
    print(f"{w:>5}: A {run(A, w)!s:5} B {run(B, w)!s:5} -> product {run(P, w)}")
ok = all(run(P, "".join(t)) == (run(A, "".join(t)) and run(B, "".join(t)))
         for n in range(0, 11) for t in product("01", repeat=n))
print("product agrees with A and B on all 2047 strings up to length 10:", ok)
for mode in ("or", "minus"):
    M = product_dfa(A, B, mode)
    print(f"same states, accepting set for {mode}: {sorted(M['acc'])}")

states: [('E', 'n'), ('E', 'y'), ('O', 'n'), ('O', 'y')]
accepting: [('E', 'y')]
    1: A True  B True  -> product True
   01: A False B True  -> product False
  001: A True  B True  -> product True
 0011: A True  B True  -> product True
 0101: A True  B True  -> product True
  100: A True  B False -> product False
product agrees with A and B on all 2047 strings up to length 10: True
same states, accepting set for or: [('E', 'n'), ('E', 'y'), ('O', 'y')]
same states, accepting set for minus: [('E', 'n')]

Regular languages are closed under many more operations. Reversal: reverse every transition of an NFA, make the old start state accepting, and add a new start state with \(\varepsilon\)-edges to the old accepting states. Homomorphism: if h maps each symbol to a string, replace each symbol in a regular expression by its image. Inverse homomorphism: given a DFA for L, build a DFA that, on reading a, simulates reading h(a). Quotient by any language and the operation 'prefixes of strings in L' also preserve regularity. These results are tools. To show that a language is regular, it is often easiest to express it as a combination of simpler languages that are obviously regular. To show that a language is not regular, we combine it with regular languages to reach a language already known to be non-regular, as lesson 4 explains.

Decision properties

Because regular languages have finite descriptions, many questions about them can be answered by algorithms. Membership: run the DFA on the string. Emptiness: is any accepting state reachable from the start state? That is graph search, linear in the size of the automaton. Finiteness: is the language infinite? It is infinite exactly when some cycle lies on a path from the start state to an accepting state, because such a cycle can be traversed any number of times. Equivalence: do two DFAs recognize the same language? Build the product, accept the pairs where exactly one component accepts, which gives the symmetric difference, and test that machine for emptiness. Equivalently, minimize both DFAs and compare them, using the uniqueness of the minimal DFA from lesson 4.

These algorithms are more than exercises. Equivalence checking for automata underlies tools that verify hardware circuits and network configurations, and the decidability of these questions for regular languages contrasts sharply with what happens for richer classes. For context-free grammars, membership and emptiness are decidable but equivalence is not, as lesson 9 shows; for Turing machines even emptiness is undecidable. The ease with which regular languages yield to algorithms is a direct consequence of their finite memory: there are only finitely many configurations to explore.

# Decision procedures for DFAs: emptiness, finiteness and equivalence.
from collections import deque

def reachable(M):
    seen, todo = {M["start"]}, deque([M["start"]])
    while todo:
        q = todo.popleft()
        for c in M["sigma"]:
            r = M["d"][(q, c)]
            if r not in seen: seen.add(r); todo.append(r)
    return seen

def is_empty(M):
    return not (reachable(M) & M["acc"])

def is_infinite(M):
    # infinite iff some cycle lies on a path from the start to an accepting state
    R = reachable(M)
    co = {q for q in R if q in M["acc"]}            # states that can reach acceptance
    changed = True
    while changed:
        changed = False
        for q in R:
            if q not in co and any(M["d"][(q, c)] in co for c in M["sigma"]):
                co.add(q); changed = True
    useful = R & co
    # look for a cycle inside the useful states (depth-first search with marks: 0 new, 1 on the stack, 2 finished)
    mark = {q: 0 for q in useful}
    def dfs(q):
        mark[q] = 1
        for c in M["sigma"]:
            r = M["d"][(q, c)]
            if r in useful and (mark[r] == 1 or (mark[r] == 0 and dfs(r))): return True
        mark[q] = 2
        return False
    return any(mark[q] == 0 and dfs(q) for q in useful)

def equivalent(M1, M2):
    # symmetric difference via the product construction, then emptiness
    st = (M1["start"], M2["start"]); seen, todo = {st}, [st]
    while todo:
        p, q = todo.pop()
        if (p in M1["acc"]) != (q in M2["acc"]): return False
        for c in M1["sigma"]:
            nxt = (M1["d"][(p, c)], M2["d"][(q, c)])
            if nxt not in seen: seen.add(nxt); todo.append(nxt)
    return True

def mod_dfa(k, acc):
    return {"sigma": "01", "start": 0, "acc": acc, "d": {(r, b): (2 * r + int(b)) % k for r in range(k) for b in "01"}}

finite = {"sigma": "01", "start": "s", "acc": {"a"},       # accepts only "1" and "10"
          "d": {("s", "1"): "a1", ("s", "0"): "x", ("a1", "0"): "a", ("a1", "1"): "x",
                ("a", "0"): "x", ("a", "1"): "x", ("x", "0"): "x", ("x", "1"): "x"}}
finite["acc"] = {"a1", "a"}
print("mod-3 = 0 language empty?   ", is_empty(mod_dfa(3, {0})))
print("no accepting states: empty?  ", is_empty(mod_dfa(3, set())))
print("mod-3 = 0 language infinite?", is_infinite(mod_dfa(3, {0})))
print("{1, 10} infinite?           ", is_infinite(finite))
six = {"sigma": "01", "start": 0, "acc": {0, 3},          # value mod 6 in {0, 3}  <=>  divisible by 3
       "d": {(r, b): (2 * r + int(b)) % 6 for r in range(6) for b in "01"}}
print("mod-6 in {0,3} equivalent to mod-3 = 0?", equivalent(six, mod_dfa(3, {0})))
print("mod-6 = 0 equivalent to mod-3 = 0?     ", equivalent(mod_dfa(6, {0}), mod_dfa(3, {0})))

mod-3 = 0 language empty?    False
no accepting states: empty?   True
mod-3 = 0 language infinite? True
{1, 10} infinite?            False
mod-6 in {0,3} equivalent to mod-3 = 0? True
mod-6 = 0 equivalent to mod-3 = 0?      False

Worked examples