Automata Theory:
DFA, NFA & Regular Expressions

The simplest model of a computer: finite memory, read input once, say yes or no.
It powers every lexer, grep, and regex engine you use.

DFA

One state at a time. One move per symbol.

NFA

Many states at once. Free ε-moves.

Regex

A tiny algebra: union, concat, star.

Kleene

All three describe exactly the same languages.

Formal definitions and proofs, plus runnable Python for every construction. All code was tested with Python 3.11+.

Roadmap WHERE WE GO

Why automata matter
Alphabets, strings, languages
DFA: formal definition
DFA example: divisible by 3
DFA in Python
NFA: formal definition
NFA example & ε-closure
NFA simulation in Python
Subset construction (NFA → DFA)
The exponential blow-up
Regular expressions: syntax & meaning
Thompson's construction (regex → NFA)
A regex engine in 50 lines
State elimination (DFA → regex)
Kleene's theorem
Closure properties & product DFA
Myhill–Nerode & minimization
Pumping lemma
Decision problems
Real regex engines & backtracking
Chomsky hierarchy

Why Automata? MOTIVATION

Where finite automata run today

Lexers: every compiler splits source into tokens with a DFA (lex, flex, re2c).
Search: grep, RE2, Rust's regex, Hyperscan.
Protocols: TCP connection states, TLS handshakes, UI flows.
Hardware: every sequential circuit is a finite state machine.
Verification: model checkers use automata over infinite words.

The big question

What can a machine compute if it has only a fixed, finite memory and reads its input once, left to right?

Answer: exactly the regular languages. We will describe them three ways and prove the three agree.

Alphabets, Strings, Languages VOCABULARY

Alphabet Σ: a finite, non-empty set of symbols. Example: Σ = {0, 1}.

String: a finite sequence over Σ. The empty string is ε. Length is |w|.

Σ*: the set of all strings, including ε. It is infinite but countable.

Language L: any subset L ⊆ Σ*.

There are uncountably many languages (2^Σ*) but only countably many machines. So most languages have no machine at all.

Operations on languages

L ∪ M union

L M = { xy : x ∈ L, y ∈ M } concatenation

L⁰ = {ε}, L^k+1 = L L^k

L* = ⋃_k≥0 L^k Kleene star

L = {"a", "ab"}
M = {"b", ""}
concat = {x + y for x in L for y in M}
print(sorted(concat))

['a', 'ab', 'abb']

Note {"a"}{"b"} ≠ {"b"}{"a"}. Concatenation is associative but not commutative. {ε} is its identity. ∅ is its zero.

Deterministic Finite Automaton FORMAL DEFINITION

A DFA is a 5-tuple M = (Q, Σ, δ, q₀, F):

Q — finite set of states
Σ — input alphabet
δ : Q × Σ → Q — total transition function
q₀ ∈ Q — start state
F ⊆ Q — accepting states

Extended transition δ̂ : Q × Σ* → Q, by recursion on the string:

δ̂(q, ε) = q δ̂(q, wa) = δ(δ̂(q, w), a)

Language of M

L(M) = { w ∈ Σ* : δ̂(q₀, w) ∈ F }

A language is regular if some DFA accepts it.

Key properties

Deterministic: exactly one next state for each (state, symbol).
Total: missing moves go to a “dead” (trap) state.
Fast: one table lookup per character, so O(|w|) time and O(1) extra space.
Memory = which state you are in. |Q| states store log₂|Q| bits.

Example: Binary Numbers Divisible by 3 DFA

Idea: the state is the remainder so far. Reading bit b turns value v into 2v + b. So remainder r becomes (2r + b) mod 3.

state (r)	on 0	on 1
→ * 0	0	1
1	2	0
2	1	2

Trace: 110 (= 6)

0 ⟶¹ 1 ⟶¹ 0 ⟶⁰ 0 accept ✓

Trace: 111 (= 7)

0 ⟶¹ 1 ⟶¹ 0 ⟶¹ 1 reject ✗

Correctness by induction on |w|: δ̂(0, w) = val(w) mod 3. The base case is val(ε) = 0. The step uses val(wb) = 2·val(w) + b.

A DFA in Python CODE

class DFA:
    def __init__(self, states, alphabet, delta, start, accept):
        self.states, self.alphabet = set(states), set(alphabet)
        self.delta, self.start, self.accept = delta, start, set(accept)

    def accepts(self, w):
        q = self.start
        for c in w:
            q = self.delta[(q, c)]   # exactly one move
        return q in self.accept

div3 = DFA(states={0, 1, 2}, alphabet="01",
           delta={(r, b): (2 * r + int(b)) % 3
                  for r in range(3) for b in "01"},
           start=0, accept={0})

print([n for n in range(20) if div3.accepts(bin(n)[2:])])
assert all(div3.accepts(bin(n)[2:]) == (n % 3 == 0)
           for n in range(1000))

[0, 3, 6, 9, 12, 15, 18]

Notes

delta is a dict keyed by (state, symbol). That is the transition table.
The loop body does one lookup. Real lexers compile this into a 2-D array or a switch.
Generalize: a DFA for “divisible by k in base b” has k states with δ(r, d) = (b·r + d) mod k.

Try it

Build a DFA over {a, b} that accepts strings with an even number of as and an odd number of bs. It needs 4 states: one for each (parity of a, parity of b) pair.

Designing a DFA: A Recipe HOW TO THINK

Four questions

What must I remember about the input so far? Keep it to a finite summary.
Make one state per summary value.
For each state and symbol, ask: how does the summary change? That is δ.
Start = the summary of the empty string. Accept = summaries that mean "yes".

Worked: binary strings containing `11`

Summary: "how much of 11 have I just seen?" Three answers: nothing (q0), one 1 (q1), all of it (q2).

state	meaning	on 0	on 1
→ q0	no progress	q0	q1
q1	last symbol was 1	q0	q2
* q2	saw 11 already	q2	q2

q2 is a trap: once you have seen 11, nothing can undo it.

Trace it by hand

input	states visited	result
`0110`	q0 → q0 → q1 → q2 → q2	accept
`1010`	q0 → q1 → q0 → q1 → q0	reject
`111`	q0 → q1 → q2 → q2	accept

Common mistakes

Missing moves. A DFA needs a move for every state and symbol. If you leave one out, you have silently added a dead state.
Forgetting ε. Ask whether the empty string should be accepted. It decides if the start state is an accept state.
Remembering too much. Storing the whole input is not finite. Keep only what the future needs.

Answer to "Try it" on the previous slide

States are pairs (a-parity, b-parity): EE, EO, OE, OO. Start at EE. Reading a flips the first letter, b flips the second. Accept only EO.

Nondeterministic Finite Automaton FORMAL DEFINITION

An ε-NFA is N = (Q, Σ, δ, q₀, F) where only δ changes:

δ : Q × (Σ ∪ {ε}) → 𝒫(Q)

Each move leads to a set of states, which may be empty. An ε-move changes state without reading input.

ε-closure E(S): all states reachable from S using only ε-moves (including S itself).

δ̂(S, ε) = E(S)

δ̂(S, wa) = E( ⋃_{q ∈ δ̂(S, w)} δ(q, a) )

Acceptance: w is accepted if some path ends in F.

L(N) = { w : δ̂({q₀}, w) ∩ F ≠ ∅ }

Two ways to picture it

Guessing: the machine magically picks the right branch whenever one exists.
Parallel: it runs every branch at once and tracks the set of live states. This view gives the algorithm.

NFAs are often much smaller and far easier to build than DFAs. They are never more powerful, as the subset construction will show.

Example: Strings Ending in “01” NFA

state	on 0	on 1
→ A	{A, B}	{A}
B	∅	{C}
* C	∅	∅

Parallel run on 1101

read	live set
(start)	{A}
1	{A}
1	{A}
0	{A, B}
1	{A, C} ← contains C: accept ✓

Branches die quietly

On 010, the B→C branch reaches C after 01. Then C has no move on the final 0, so that branch dies. The final set is {A, B}, with no C. Reject.

Simulating an NFA in Python SET OF STATES

EPS = ""                      # label for epsilon moves

class NFA:
    def __init__(self, delta, start, accept):
        self.delta, self.start = delta, start
        self.accept = frozenset(accept)

    def closure(self, states):    # E(S), a DFS on eps-edges
        seen, stack = set(states), list(states)
        while stack:
            q = stack.pop()
            for r in self.delta.get((q, EPS), ()):
                if r not in seen:
                    seen.add(r); stack.append(r)
        return frozenset(seen)

    def step(self, states, c):
        return self.closure({r for q in states
                             for r in self.delta.get((q, c), ())})

    def accepts(self, w):
        cur = self.closure({self.start})
        for c in w:
            cur = self.step(cur, c)
        return bool(cur & self.accept)

ends01 = NFA(delta={("A", "0"): {"A", "B"},
                    ("A", "1"): {"A"},
                    ("B", "1"): {"C"}},
             start="A", accept={"C"})

print([w for w in ["01", "1101", "010", "0", ""]
       if ends01.accepts(w)])

['01', '1101']

Cost: with m states and edges, each step is O(m). So the whole run is O(m · |w|). That is linear in the input and never exponential.

This is Ken Thompson's 1968 algorithm. It is the core of grep, RE2, and Go's regexp.

Subset Construction: NFA → DFA RABIN & SCOTT 1959

Theorem. For every ε-NFA N there is a DFA D with L(D) = L(N).

Construction. Each DFA state is a set of NFA states.

Q_D ⊆ 𝒫(Q_N)
q_D = E({q₀})
δ_D(S, a) = E(⋃_q∈S δ_N(q, a))
F_D = { S : S ∩ F_N ≠ ∅ }

Proof idea: by induction on |w|, δ̂_D(q_D, w) = δ̂_N({q₀}, w). So D is in state S exactly when S is N's live set.

def to_dfa(nfa, alphabet):
    start = nfa.closure({nfa.start})
    delta, seen, todo = {}, {start}, [start]
    while todo:                    # only reachable subsets
        S = todo.pop()
        for c in alphabet:
            T = nfa.step(S, c)
            delta[(S, c)] = T
            if T not in seen:
                seen.add(T); todo.append(T)
    accept = {S for S in seen if S & nfa.accept}
    return DFA(seen, alphabet, delta, start, accept)

d = to_dfa(ends01, "01")
print(sorted(sorted(s) for s in d.states))

[['A'], ['A', 'B'], ['A', 'C']]

DFA state	on 0	on 1
→ {A}	{A,B}	{A}
{A,B}	{A,B}	{A,C}
* {A,C}	{A,B}	{A}

Worked Example: ε-NFA → DFA for ab STEP BY STEP

The steps

Start = E({q0}) = {q0, q1}. It holds q1, so it accepts.
From {q0,q1} on a: only q0 moves, to q0. Close it: {q0,q1}.
From {q0,q1} on b: only q1 moves, to q1. Close it: {q1}. New state.
From {q1} on a: no moves, so ∅. New state.
From {q1} on b: {q1}. From ∅: always ∅. Done.

DFA state	on a	on b	accept?
→ {q0, q1}	{q0, q1}	{q1}	yes
{q1}	∅	{q1}	yes
∅	∅	∅	no (dead)

Read the result

{q0,q1} means "still reading a's". {q1} means "now reading b's". ∅ means "saw an a after a b". Only 3 of the 4 subsets are reachable, so we never build {q0}.

Common mistakes

Starting at {q0} instead of E({q0}). Then the DFA rejects ε, which is wrong.
Taking the closure only once. Close after every move.
Dropping ∅. It is a real DFA state: the dead state.

The Exponential Blow-Up Is Real LOWER BOUND

Subsets of an n-state NFA: up to 2ⁿ. Sometimes you truly need all of them.

Language L_n = strings over {0,1} whose n-th symbol from the end is 1.

L_n = (0|1)* 1 (0|1)ⁿ⁻¹

An NFA needs only n + 1 states. It guesses the right 1, then counts n − 1 more symbols.

Claim. Every DFA for L_n has at least 2ⁿ states.

Proof. Take two different strings x ≠ y of length n. They differ at some position i, say x_i = 1 and y_i = 0. Append z = 0ⁱ⁻¹. Then xz ∈ L_n but yz ∉ L_n. So a DFA must reach different states on x and y. There are 2ⁿ such strings. ∎

for n in range(1, 9):
    nfa = compile_regex("(0|1)*1" + "(0|1)" * (n - 1))
    dfa = to_dfa(nfa, "01")
    print(n, len(dfa.states), len(minimize(dfa).states))

Columns: n, subset DFA size, minimal DFA size. The minimal DFA hits exactly 2ⁿ. This is why real engines simulate NFAs lazily and cache DFA states on demand.

Regular Expressions SYNTAX & SEMANTICS

Syntax (inductive). Over alphabet Σ:

R ::= ∅ | ε | a | R₁ | R₂ | R₁R₂ | R*

Precedence: * binds tightest, then concatenation, then |.

Semantics L(R) ⊆ Σ*

L(∅) = ∅ L(ε) = {ε} L(a) = {a}

L(R|S) = L(R) ∪ L(S)

L(RS) = L(R) L(S) L(R*) = L(R)*

Sugar: R+ = RR*, R? = R|ε, [abc] = a|b|c, . = any symbol. None adds power.

Regex	Language
`(0\|1)*01`	binary strings ending in 01
`(a\|b)*abb`	strings ending in abb
`1(01+)`	every 0 is immediately followed by a 1
`(0\|1(010)1)*`	binary multiples of 3 (from our DFA)
`[a-z_][a-z0-9_]*`	identifiers

Algebraic laws (Kleene algebra)

R|S = S|R R|R = R R∅ = ∅

R(S|T) = RS|RT (R*)* = R*

R* = ε | RR* (R|S)* = (R*S*)*

Thompson's Construction: Regex → ε-NFA STRUCTURAL INDUCTION

Build one small fragment per regex case. Each fragment has one start state and one accept state. Glue fragments with ε-edges.

A Regex Engine in ~50 Lines PARSER + THOMPSON

import itertools

def compile_regex(pattern):
    """Thompson: literals, |, *, +, ?, ( )."""
    delta, ids, pos = {}, itertools.count(), 0
    def new(): return next(ids)
    def edge(a, sym, b): delta.setdefault((a, sym), set()).add(b)
    def peek(): return pattern[pos] if pos < len(pattern) else None
    def eat():
        nonlocal pos
        pos += 1
        return pattern[pos - 1]

    def alt():                     # alt := cat ('|' cat)*
        s, e = cat()
        while peek() == "|":
            eat(); s2, e2 = cat()
            ns, ne = new(), new()
            edge(ns, EPS, s); edge(ns, EPS, s2)
            edge(e, EPS, ne); edge(e2, EPS, ne)
            s, e = ns, ne
        return s, e

    def cat():                     # cat := post*
        s = e = new()
        while peek() not in (None, "|", ")"):
            s2, e2 = post()
            edge(e, EPS, s2); e = e2
        return s, e

    def post():                    # post := atom ('*'|'+'|'?')*
        s, e = atom()
        while peek() in ("*", "+", "?"):
            op = eat()
            ns, ne = new(), new()
            edge(ns, EPS, s); edge(e, EPS, ne)
            if op in "*?": edge(ns, EPS, ne)   # may skip
            if op in "*+": edge(e, EPS, s)     # may repeat
            s, e = ns, ne
        return s, e

    def atom():
        if peek() == "(":
            eat(); s, e = alt(); eat()   # consume ')'
            return s, e
        s, e = new(), new()
        edge(s, eat(), e)
        return s, e

    start, end = alt()
    return NFA(delta, start, {end})

Tested against Python's re.fullmatch on every string up to length 6 over {a,b,c} for (a|b)*abb, a+b?, (ab|c)*, a(b|)c, ((a|b)(a|b))*.

Back Again: Automaton → Regex STATE ELIMINATION

Kleene's recursion (McNaughton–Yamada). Number the states 1..n. Let R^(k)_ij be the strings that go from i to j using only states ≤ k in the middle.

R^(k)_ij = R^(k−1)_ij | R^(k−1)_ik (R^(k−1)_kk)* R^(k−1)_kj

Then L(M) = ⋃_{f ∈ F} R⁽ⁿ⁾_1f. Same shape as Floyd–Warshall.

Arden's lemma. If ε ∉ L(A), then X = AX | B has the unique solution X = A*B. Solve the state equations like linear algebra.

By hand: eliminate one state at a time

To remove state k with self-loop S: for each path p ⟶^A k ⟶^B q, add edge p ⟶^{A S* B} q. Union parallel edges.

Divisible-by-3 DFA

Remove state 2. It has self-loop 1, entry 0 from 1, and exit 0 back to 1. So state 1 gets a new loop 01*0. Now remove state 1. Its loop from 0 is 1(01*0)*1. Result:

(0 | 1(01*0)*1)*

import re
pat = re.compile(r"(0|1(01*0)*1)*")
assert all(bool(pat.fullmatch(bin(n)[2:])) == (n % 3 == 0)
           for n in range(5000))

Kleene's Theorem (1956) THE BIG EQUIVALENCE

Theorem. For any language L ⊆ Σ*, the following are equivalent:

L = L(R) for some regular expression R.
L = L(N) for some ε-NFA N.
L = L(D) for some DFA D.

1 ⇒ 2

Thompson's construction. Induction on regex structure. Size O(|R|).

2 ⇒ 3

Subset construction. Size up to 2^|Q|, and that bound is tight.

3 ⇒ 1

State elimination or Kleene's R^(k)_ij. The regex can be exponentially long.

Why it matters

Pick the view that suits the job. Write patterns as regexes. Build and combine as NFAs. Run and minimize as DFAs.

Other characterizations

Regular languages are also exactly: right-linear grammars (Type 3), finite-index Myhill–Nerode relations, languages recognized by finite monoids, and sets definable in monadic second-order logic over strings (Büchi–Elgot–Trakhtenbrot).

Closure Properties & the Product DFA BUILD BIG FROM SMALL

Operation	Construction
Union L ∪ M	Regex `\|`, or product DFA with OR
Intersection L ∩ M	Product DFA with AND
Complement Σ* − L	Total DFA, swap F and Q − F
Difference L − M	L ∩ ¬M
Concat, star	Thompson fragments
Reversal L^R	Flip every edge. Swap start and accept. With several accept states, add a new start with ε-edges to each.
Homomorphism	Substitute a regex for each symbol

Product: Q = Q_A × Q_B, δ((p,q), a) = (δ_A(p,a), δ_B(q,a)). Run both machines in lock-step.

def product(A, B, op):
    states = {(p, q) for p in A.states for q in B.states}
    delta = {((p, q), c): (A.delta[(p, c)], B.delta[(q, c)])
             for (p, q) in states for c in A.alphabet}
    accept = {(p, q) for (p, q) in states
              if op(p in A.accept, q in B.accept)}
    return DFA(states, A.alphabet, delta,
               (A.start, B.start), accept)

even_len = DFA({0, 1}, "01",
               {(q, c): 1 - q for q in (0, 1) for c in "01"},
               0, {0})
both = product(div3, even_len, lambda x, y: x and y)
print([bin(n)[2:] for n in range(40)
       if both.accepts(bin(n)[2:])][:6])

['11', '1001', '1100', '1111', '100001', '100100']

Multiples of 3 whose binary form has even length. Intersection is easy for DFAs but has no direct regex operator.

Myhill–Nerode & DFA Minimization THE CANONICAL DFA

Nerode equivalence. Two strings are equivalent for L if no suffix can tell them apart:

x ≡_L y ⇔ ∀z ∈ Σ*: (xz ∈ L ⇔ yz ∈ L)

Myhill–Nerode Theorem (1958).

L is regular iff ≡_L has finitely many classes.
The number of classes equals the size of the minimal DFA.
The minimal DFA is unique up to renaming states.

So you can test regex equality by minimizing both DFAs and comparing. It also proves non-regularity: a, aa, aaa, … are pairwise inequivalent for {aⁿbⁿ}.

Moore's partition refinement

def minimize(dfa):             # assumes all states reachable
    alpha = sorted(dfa.alphabet)
    P = [b for b in (set(dfa.accept), dfa.states - dfa.accept) if b]
    while True:
        where = {q: i for i, blk in enumerate(P) for q in blk}
        newP = []
        for blk in P:          # split by "where do my moves go?"
            groups = {}
            for q in blk:
                sig = tuple(where[dfa.delta[(q, c)]] for c in alpha)
                groups.setdefault(sig, set()).add(q)
            newP.extend(groups.values())
        if len(newP) == len(P):
            break
        P = newP
    where = {q: i for i, blk in enumerate(P) for q in blk}
    delta = {(where[q], c): where[dfa.delta[(q, c)]]
             for q in dfa.states for c in alpha}
    return DFA(range(len(P)), alpha, delta, where[dfa.start],
               {where[q] for q in dfa.accept})

big = to_dfa(compile_regex("(a|b)*abb"), "ab")
print(len(big.states), "->", len(minimize(big).states))

5 -> 4

Moore: O(n²|Σ|). Hopcroft (1971): O(n |Σ| log n).

Minimization by Hand WORKED EXAMPLE

This 5-state DFA accepts strings over {a, b} that end in ab. It has extra states. Let us find them.

state	on a	on b
→ A	B	A
B	D	C
* C	D	A
D	B	E
* E	B	A

Idea

Start by trusting only one fact: accept states differ from the rest. Then split any group whose members move to different groups on some symbol. Stop when nothing splits.

Round 0

Accept vs. non-accept: F = {C, E}, N = {A, B, D}.

Round 1: where does each state go?

state	a →	b →	group pattern
A	B (N)	A (N)	N, N
B	D (N)	C (F)	N, F
D	B (N)	E (F)	N, F
C	D (N)	A (N)	N, N
E	B (N)	A (N)	N, N

A differs from B and D, so N splits: {A}, {B, D}, {C, E}.

Round 2

B and D both go to {B,D} on a and to {C,E} on b. C and E both go to {B,D}, then {A}. No split. Done: 3 states.

Meaning of the 3 states: "no progress", "just read a", "just read ab". The minimize code above gives the same result.

The Pumping Lemma PROVING A LANGUAGE IS NOT REGULAR

Lemma. If L is regular, there is a p ≥ 1 such that every w ∈ L with |w| ≥ p splits as w = xyz with:

|xy| ≤ p, |y| ≥ 1, ∀i ≥ 0: xyⁱz ∈ L

Proof. Let p = |Q| of a DFA for L. Reading the first p symbols of w visits p + 1 states. By pigeonhole, some state q repeats. Let y be the part read between the two visits. It is a loop at q. So you can go round it 0, 1, 2, … times and still end in the same accept state. ∎

Example: L = { aⁿbⁿ : n ≥ 0 } is not regular

Suppose it is, with pumping length p.
Pick w = a^pb^p ∈ L.
Since |xy| ≤ p, both x and y are all as. So y = a^k with k ≥ 1.
Pump down: xz = a^p−kb^p ∉ L.
Contradiction. ∎

Careful

The lemma is only a necessary condition. Some non-regular languages still pump. Myhill–Nerode gives an exact test.

Also not regular: balanced parentheses, {ww}, primes in unary, {a^n²}. Moral: a finite machine cannot count without limit.

The Pumping Lemma as a Game YOU VS. THE ADVERSARY

Four moves

Adversary picks the pumping length p.
You pick a string s ∈ L with |s| ≥ p.
Adversary splits s = xyz with |xy| ≤ p and |y| ≥ 1.
You pick i ≥ 0. You win if xyⁱz ∉ L.

If you can win against every p and every split, L is not regular.

Common mistakes

Choosing the split yourself. The adversary picks x, y, z. You must beat all of them.
Picking a number for p. Keep p as a symbol, like a^pb^p.
Using it to prove a language regular. Passing the pumping test proves nothing.

Worked: L = { aⁱb^j : i > j }

Adversary says p.
You pick s = a^p+1b^p. It is in L and long enough.
Any split has |xy| ≤ p. So y = a^k with k ≥ 1.
Try i = 2: a^p+1+kb^p. Still in L. That move loses.
Try i = 0: a^p+1−kb^p. Now p+1−k ≤ p, so it is not in L. You win. ∎

Lesson: pumping up is not always the answer. Here, only pumping down works.

Check yourself: is {aⁿb^m : n, m ≥ 0} regular?

Yes. It is just a*b*. Nothing ties n to m, so there is nothing to count. The pumping lemma cannot be used against it.

Check yourself: for {aⁿbⁿ}, why is s = a^p/2b^p/2 a bad pick?

The adversary may then put y across the border, like ab. Pumping gives ...abab..., which is out of L, but you must also handle every other split. With a^pb^p, the rule |xy| ≤ p forces y into the a's, so there is just one case.

Decision Problems EVERYTHING IS DECIDABLE

Question	Algorithm	Cost
Membership w ∈ L?	Run the DFA / simulate the NFA	O(\|w\|) / O(m\|w\|)
Emptiness L = ∅?	Can start reach any accept state?	linear (BFS)
Finiteness	Is there a cycle on some start→accept path?	linear
Equivalence (DFA)	(A ⊕ B) = ∅, or compare minimal DFAs	polynomial
Universality (NFA)	L = Σ*?	PSPACE-complete
Equivalence (regex)	via subset construction	PSPACE-complete

def is_empty(dfa):
    seen, todo = {dfa.start}, [dfa.start]
    while todo:
        q = todo.pop()
        if q in dfa.accept:
            return False
        for c in dfa.alphabet:
            r = dfa.delta[(q, c)]
            if r not in seen:
                seen.add(r); todo.append(r)
    return True

def equivalent(A, B):          # symmetric difference is empty
    return is_empty(product(A, B, lambda x, y: x != y))

abb = to_dfa(compile_regex("(a|b)*abb"), "ab")
ab  = to_dfa(compile_regex("(a|b)*ab"),  "ab")
print(equivalent(abb, minimize(abb)), equivalent(abb, ab))

True False

Compare Turing machines: none of these questions is decidable there (Rice's theorem). Finite memory buys you complete analyzability.

Real Regex Engines: Automata vs. Backtracking PRACTICE

Backtracking (Python `re`, PCRE, Java, JS)

Tries one branch at a time, depth-first. On failure it rewinds. Worst case is exponential in the input length.

import re, time
for n in (18, 20, 22):
    t = time.perf_counter()
    re.match(r"(a+)+$", "a" * n + "b")
    print(n, f"{time.perf_counter() - t:.3f}s")

18 0.010s
20 0.038s
22 0.150s      # x4 every 2 chars; n=40 takes days

This is “ReDoS”. It took down Stack Overflow in 2016 and Cloudflare in 2019.

Automata (RE2, Go, Rust `regex`, `grep`)

Thompson NFA simulation plus a lazily built DFA cache. Guaranteed O(m · |w|).

nfa = compile_regex("(a+)+")
nfa.accepts("a" * 22 + "b")   # ~0.05 ms, and linear in n

Why backtrack at all?

Features beyond regular languages. Backreferences like (a*)b\1 match {aⁿbaⁿ}, which is not regular. Matching with backreferences is NP-complete. Lookaround and lazy quantifiers are also easier to add to a backtracker.

re.fullmatch(r"(a*)b\1", "aaabaaa")   # match
re.fullmatch(r"(a*)b\1", "aaabaa")    # None

Beyond Regular: The Chomsky Hierarchy MORE MEMORY, MORE POWER

Type	Languages	Machine	Example
3	Regular	DFA / NFA	`(ab)*`
2	Context-free	Pushdown automaton (NFA + stack)	aⁿbⁿ, balanced parens
1	Context-sensitive	Linear-bounded automaton	aⁿbⁿcⁿ
0	Recursively enumerable	Turing machine	halting set

Each level strictly contains the one above. Regular ⊂ CFL ⊂ CSL ⊂ RE.

Practical link: a lexer (regular) splits code into tokens. A parser (context-free) builds the syntax tree. Nested structure needs a stack. That is exactly why you should not parse HTML with a regex.

Check Yourself PRACTICE

Try each one before you open the answer.

1. How many states does a DFA need for binary numbers divisible by 5?

Five, one per remainder 0–4. Reading bit c sends remainder r to (2r + c) mod 5. All five remainders are distinguishable, so none can merge.

2. Over {0,1}, is "as many 01s as 10s" regular?

Yes, surprisingly. The two counts can differ by at most 1. They are equal exactly when the string is empty or starts and ends with the same symbol. That needs only a few states.

3. To complement an NFA, can you just swap accept and non-accept states?

No. An NFA accepts if some path accepts. After the swap, a string with one accepting and one rejecting path is still accepted. Convert to a DFA first, then swap.

4. Write a regex for binary strings with no two 1s in a row.

(0 | 10)* (ε | 1). Every 1 is followed by a 0, except maybe a final 1.

5. L is regular and M is not. Is L ∪ M ever regular?

Yes, it can be. Take L = Σ*. Then L ∪ M = Σ*, which is regular. Closure only works when both inputs are regular.

Mistakes students make

Mistake	Fix
"NFAs are more powerful than DFAs."	Same power. NFAs are only smaller.
"Every subset of a regular language is regular."	No: {aⁿbⁿ} ⊆ ab.
"Infinite language means not regular."	`a` is infinite and regular. Unbounded counting* is the problem.
"The pumping lemma shows L is regular."	It can only show non-regularity.
Using `\1` backreferences as "regex".	They go beyond regular. `(a*)b\1` is not regular.

6. Is {w : |w| is a multiple of 3 or of 5} regular?

Yes. Build a DFA for each part (3 and 5 states). The union is regular by closure. The product DFA has 15 states, one per (length mod 3, length mod 5).

Summary TAKE-AWAYS

Remember

DFA: one state, one move per symbol, linear time.
NFA: sets of states and ε-moves. Same power, can be exponentially smaller.
Regex ↔ NFA ↔ DFA (Kleene's theorem).
Myhill–Nerode gives a unique minimal DFA.
Pumping lemma: finite memory cannot count without limit.

Conversion	Algorithm	Size
Regex → NFA	Thompson	O(n)
NFA → DFA	Subset construction	O(2ⁿ)
DFA → min DFA	Moore / Hopcroft	≤ n
DFA → Regex	State elimination	O(4ⁿ) worst

Glossary QUICK REFERENCE

Term	Meaning
Alphabet Σ	A finite set of symbols, like {0, 1}.
String / word	A finite sequence of symbols. ε is the empty string.
Σ*	All strings over Σ, including ε.
Language	Any set of strings, so a subset of Σ*.
DFA	Finite automaton with exactly one move per state and symbol.
NFA / ε-NFA	May have 0, 1 or many moves, and ε-moves. Accepts if some path does.
ε-closure E(S)	States reachable from S by ε-moves alone.
Dead (trap) state	A non-accepting state you can never leave.
Regular language	Accepted by some DFA. Same as: described by a regex.

Term	Meaning
Subset construction	NFA → DFA. Each DFA state is a set of NFA states.
Thompson's construction	Regex → ε-NFA, one small piece per operator.
State elimination	Automaton → regex, removing one state at a time.
Kleene's theorem	Regex, NFA and DFA describe the same languages.
Closure property	An operation that keeps regular languages regular.
Product DFA	Runs two DFAs at once. Gives ∩, ∪, difference.
Nerode equivalence	x ≡ y if no suffix tells them apart.
Minimal DFA	Fewest states for a language. Unique up to renaming.
Pumping length p	Long strings (\|s\| ≥ p) have a loop y near the start.

Automata Theory:DFA, NFA & Regular Expressions

DFA

NFA

Regex

Kleene

Roadmap WHERE WE GO

Why Automata? MOTIVATION

Where finite automata run today

The big question

Alphabets, Strings, Languages VOCABULARY

Deterministic Finite Automaton FORMAL DEFINITION

Key properties

Example: Binary Numbers Divisible by 3 DFA

Trace: 110 (= 6)

Trace: 111 (= 7)

A DFA in Python CODE

Notes

Try it

Designing a DFA: A Recipe HOW TO THINK

Four questions

Worked: binary strings containing 11

Trace it by hand

Common mistakes

Nondeterministic Finite Automaton FORMAL DEFINITION

Two ways to picture it

Example: Strings Ending in “01” NFA

Parallel run on 1101

Branches die quietly

Simulating an NFA in Python SET OF STATES

Subset Construction: NFA → DFA RABIN & SCOTT 1959

Worked Example: ε-NFA → DFA for a*b* STEP BY STEP

The steps

Read the result

Common mistakes

The Exponential Blow-Up Is Real LOWER BOUND

Regular Expressions SYNTAX & SEMANTICS

Thompson's Construction: Regex → ε-NFA STRUCTURAL INDUCTION

A Regex Engine in ~50 Lines PARSER + THOMPSON

Back Again: Automaton → Regex STATE ELIMINATION

By hand: eliminate one state at a time

Divisible-by-3 DFA

Kleene's Theorem (1956) THE BIG EQUIVALENCE

1 ⇒ 2

2 ⇒ 3

3 ⇒ 1

Why it matters

Other characterizations

Closure Properties & the Product DFA BUILD BIG FROM SMALL

Myhill–Nerode & DFA Minimization THE CANONICAL DFA

Moore's partition refinement

Minimization by Hand WORKED EXAMPLE

Idea

Round 0

Round 1: where does each state go?

Round 2

The Pumping Lemma PROVING A LANGUAGE IS NOT REGULAR

Example: L = { anbn : n ≥ 0 } is not regular

Careful

The Pumping Lemma as a Game YOU VS. THE ADVERSARY

Four moves

Common mistakes

Worked: L = { aibj : i > j }

Decision Problems EVERYTHING IS DECIDABLE

Real Regex Engines: Automata vs. Backtracking PRACTICE

Backtracking (Python re, PCRE, Java, JS)

Automata (RE2, Go, Rust regex, grep)

Why backtrack at all?

Beyond Regular: The Chomsky Hierarchy MORE MEMORY, MORE POWER

Check Yourself PRACTICE

Mistakes students make

Summary TAKE-AWAYS

Remember

Further reading

Glossary QUICK REFERENCE

Automata Theory:
DFA, NFA & Regular Expressions

Worked: binary strings containing `11`

Worked Example: ε-NFA → DFA for ab STEP BY STEP

Example: L = { aⁿbⁿ : n ≥ 0 } is not regular

Worked: L = { aⁱb^j : i > j }

Backtracking (Python `re`, PCRE, Java, JS)

Automata (RE2, Go, Rust `regex`, `grep`)