Regular Expressions & Finite Automata

Theory of Computation asks what machines can and cannot do, and it starts with the weakest useful machine: one with a fixed, finite amount of memory.

A finite automaton remembers nothing except which state it is in. It has no counter, no stack, no tape — the entire history of the input must be compressed into one of finitely many states before the next symbol arrives.

That single restriction generates the whole theory. A language is regular precisely when the strings read so far can be sorted into finitely many classes such that any two strings in the same class are interchangeable for every possible future.

So the diagnostic question for any language is: how many distinct situations must be told apart? If the answer is a fixed finite number, a finite automaton exists and the language is regular. If the number grows with the input, no finite automaton can work.

Counting matched brackets requires distinguishing unboundedly many depths, so it is not regular. Counting the number of as modulo 3 requires distinguishing only three situations, so it is.

The second organising fact is that regular expressions and finite automata describe exactly the same languages. Kleene's theorem makes them interchangeable, so a question may be attacked from whichever side is easier.

1. Deterministic Finite Automata

A DFA is a five-tuple: states, alphabet, transition function, start state and accepting states.

The defining property is that the transition function is total and single-valued: for every state and every input symbol there is exactly one next state. No choices, no missing edges.

A string is accepted if reading it from the start state ends in an accepting state. The language of the automaton is the set of all accepted strings.

A DFA with a missing transition is not a DFA. The usual repair is a dead state — a non-accepting state with self-loops on every symbol — which absorbs anything that has already failed.

Because the machine is deterministic, tracing a string takes exactly one step per symbol, so membership testing is $O(n)$ with a constant that does not depend on the automaton's size.

A Moore machine attaches an output to each state and a Mealy machine to each transition, which makes them transducers rather than acceptors, but the underlying state machinery is identical to a DFA's.

2. Nondeterministic Finite Automata

An NFA relaxes the transition function into a relation: a state may have several transitions on a symbol, or none.

A string is accepted if at least one computation path ends in an accepting state. Nondeterminism is not a coin flip; it is a guarantee that if any path succeeds, the machine accepts.

An $ϵ$-NFA additionally allows transitions that consume no input, which makes constructions much easier to draw.

The central theorem is that NFAs and DFAs recognise exactly the same languages. Nondeterminism buys convenience, never power.

The proof is the subset construction. Each DFA state is a set of NFA states — precisely the set the NFA could currently be in.

The DFA's start state is the $ϵ$-closure of the NFA's start state. The transition on a symbol takes the union of the NFA transitions from every state in the current set, then closes under $ϵ$.

An $n$-state NFA can require up to $2^n$ DFA states, and that bound is tight: languages exist for which every equivalent DFA is exponentially larger.

The standard family is "the $k$-th symbol from the end is a", which an NFA recognises with $k+1$ states by guessing when the tail begins, while any DFA must remember the last $k$ symbols and therefore needs $2^k$ states.

3. Regular Expressions

A regular expression is built from three operations over an alphabet.

The star includes zero repetitions, so the empty string belongs to $r^{\ast }$ for every $r$, including the empty language. This is the most frequently missed detail in expression questions.

Precedence runs star highest, then concatenation, then union, so $a{b}^{\ast }$ means $a$ followed by any number of $b$s, not $(ab{)}^{\ast }$.

Several identities are examined directly.

$(r^{\ast }{)}^{\ast }=r^{\ast }{r}^{\ast }{r}^{\ast }=r^{\ast }(r+s{)}^{\ast }=(r^{\ast }{s}^{\ast }{)}^{\ast }$

But $(rs{)}^{\ast }\ne r^{\ast }{s}^{\ast }$, since the left side alternates the two while the right allows all of $r$ before any of $s$.

Kleene's theorem states that a language is describable by a regular expression exactly when some finite automaton recognises it. The proof gives both directions constructively: Thompson's construction builds an $ϵ$-NFA from an expression, and state elimination extracts an expression from an automaton.

Thompson's construction is compositional, building a small $ϵ$-NFA fragment for each operator and gluing them together. Each fragment has exactly one start and one accepting state, which is what makes the gluing uniform.

The size grows linearly: an expression with $n$ symbols and operators yields an $ϵ$-NFA with at most $2n$ states. That linearity is why regular-expression engines compile so cheaply.

State elimination runs the other way, repeatedly deleting a state and relabelling the edges that bypassed it with expressions that account for any loops on the removed state. When only a start and an accepting state remain, the label between them is the answer.

The order of elimination affects the size of the resulting expression enormously, though never its correctness, which is why extracted expressions are often far uglier than a hand-written equivalent.

4. Closure Properties

Regular languages are closed under every operation likely to be asked about.

Complementation requires a DFA, not an NFA. Swapping accepting states in an NFA does not complement the language, because a string may have both an accepting and a rejecting path — so both the original and the "complement" would accept it.

The product construction handles union and intersection together. The state set is the Cartesian product, so an $m$-state and an $n$-state automaton give $mn$ states, and only the accepting set differs: both components accepting for intersection, either component for union.

5. Minimisation

Every regular language has a unique minimal DFA, up to renaming of states.

The algorithm has two phases.

First, remove unreachable states — those no string can reach from the start. They affect nothing and are simply deleted.

Second, merge equivalent states. Two states are equivalent if no string distinguishes them, meaning for every string, both lead to accepting states or both to non-accepting ones.

The table-filling method computes this by refinement. Mark every pair with one accepting and one non-accepting state as distinguishable. Then repeatedly mark a pair if some symbol sends it to an already-marked pair. Stop when a full pass marks nothing new, and merge all unmarked pairs.

Stopping early is the standard error, because pairs that survive one round can be separated in the next.

Hopcroft's algorithm achieves the same result in $O(n\log n)$ by refining partitions rather than filling a table, which matters when the automaton is large. The answer is identical either way, since the minimal DFA is unique.

A useful sanity check after minimising is that the number of remaining states should match the number of Myhill-Nerode classes, if those can be counted independently.

6. The Myhill-Nerode Theorem

The theorem explains why the minimal DFA is unique and gives the sharpest tool for proving non-regularity.

Two strings $x$ and $y$ are indistinguishable with respect to a language $L$ if, for every string $z$, either both $xz$ and $yz$ are in $L$ or neither is.

This is an equivalence relation, and the theorem says $L$ is regular exactly when it has finitely many equivalence classes. Moreover, the number of classes equals the number of states in the minimal DFA.

That gives a proof technique for non-regularity that is often cleaner than the pumping lemma: exhibit infinitely many pairwise distinguishable strings.

For the language of balanced brackets, the strings (, ((, ((( and so on are pairwise distinguishable, since appending $k$ closing brackets accepts exactly one of them. Infinitely many classes exist, so the language is not regular.

The theorem is an exact characterisation, so it can prove regularity as well as refute it — something the pumping lemma cannot do.

7. Worked Examples

Example 1. Construct a DFA over $\{a,b\}$ accepting strings where the number of $a$s is divisible by 3.

The only thing that must be remembered is the count of $a$s modulo 3, which takes three values.

States $q_0$, $q_1$, $q_2$ represent remainders 0, 1 and 2. The start state is $q_0$, which is also the only accepting state, since the empty string has zero $a$s.

On $a$, each state advances: $q_0\to q_1\to q_2\to q_0$.

On $b$, every state loops to itself, because $b$ does not change the count.

Three states suffice, and three are necessary. The strings $ϵ$, $a$ and $aa$ are pairwise distinguishable — appending $aa$, $a$ and $ϵ$ respectively accepts exactly one of them — so by Myhill-Nerode the minimal DFA has exactly 3 states.

Note how the count itself is never stored, only its remainder. That compression from an unbounded quantity to a bounded one is exactly what makes the language regular.

Example 2. Convert the NFA with states $\{p,q\}$, start $p$, accepting $q$, and transitions $\delta (p,a)=\{p,q\}$, $\delta (p,b)=\{p\}$, $\delta (q,b)=\{q\}$ into a DFA.

Apply the subset construction, starting from $\{p\}$.

From $\{p\}$ on $a$: the NFA can be in $p$ or $q$, giving $\{p,q\}$. On $b$: only $p$, giving $\{p\}$.

From $\{p,q\}$ on $a$: from $p$ we get $\{p,q\}$, from $q$ there is no $a$ transition, so the union is $\{p,q\}$. On $b$: from $p$ we get $\{p\}$, from $q$ we get $\{q\}$, so the union is $\{p,q\}$.

No new subsets appear, so the DFA has two reachable states: $\{p\}$ and $\{p,q\}$.

Accepting states are those containing $q$, so only $\{p,q\}$ accepts.

The DFA stays in $\{p\}$ until it sees an $a$, then remains in $\{p,q\}$ forever. The language is therefore strings containing at least one $a$.

Only 2 of the possible 4 subsets were reachable, which is typical: the exponential bound is worst case, not usual case.

Example 3. Show that a DFA for "the third symbol from the end is $a$" needs at least 8 states over $\{a,b\}$.

An NFA does this with 4 states, guessing nondeterministically when the last three symbols begin.

For the DFA lower bound, use Myhill-Nerode. Consider the eight strings of length 3 over $\{a,b\}$.

Take any two distinct such strings $x$ and $y$. They differ in some position $i$ from the left, say $x$ has $a$ and $y$ has $b$ there.

Append $z$ of length $i-1$. Now the third-from-last symbol of $xz$ is position $i$ of $x$ — provided we choose the length so that the differing position lands third from the end.

Concretely, if they differ in the first symbol, append nothing; the third from last of a 3-string is its first symbol, so exactly one is accepted. If they differ in the second, append one symbol. If in the third, append two.

In every case a distinguishing suffix exists, so all eight strings are pairwise inequivalent and the minimal DFA has at least 8 states.

Eight also suffice: the state remembers the last three symbols. So the minimum is exactly $2^3=8$, against 4 for the NFA — the exponential gap in miniature.

Example 4. Minimise the DFA with states $\{A,B,C,D,E\}$, start $A$, accepting $\{C,D\}$, and transitions: $A\to B$ on 0 and $C$ on 1; $B\to A$ on 0 and $D$ on 1; $C\to E$ on 0 and $C$ on 1; $D\to E$ on 0 and $D$ on 1; $E\to E$ on both.

First check reachability. From $A$ we reach $B$ and $C$; from $B$ we reach $D$; from $C$ and $D$ we reach $E$. All five states are reachable.

Now the table-filling method. Mark every pair with exactly one accepting state: $(A,C)$, $(A,D)$, $(B,C)$, $(B,D)$, $(C,E)$, $(D,E)$.

Unmarked so far: $(A,B)$, $(A,E)$, $(B,E)$, $(C,D)$.

Round 1. For $(A,B)$: on 0 they go to $B$ and $A$, giving the unmarked pair $(A,B)$; on 1 they go to $C$ and $D$, giving the unmarked pair $(C,D)$. Nothing forces a mark.

For $(A,E)$: on 0 they go to $B$ and $E$, giving $(B,E)$, unmarked; on 1 they go to $C$ and $E$, giving $(C,E)$, which is marked. So mark $(A,E)$.

For $(B,E)$: on 1 they go to $D$ and $E$, giving $(D,E)$, marked. So mark $(B,E)$.

For $(C,D)$: on 0 both go to $E$, giving $(E,E)$, not a distinguishing pair; on 1 they go to $C$ and $D$, giving $(C,D)$ itself. Nothing forces a mark.

Round 2. Re-examine $(A,B)$: its successors are $(A,B)$ and $(C,D)$, both still unmarked. No mark. Re-examine $(C,D)$: same situation. No mark.

A full pass produced nothing new, so the algorithm stops.

Merge $A$ with $B$, and $C$ with $D$. The minimal DFA has three states: $\{A,B\}$, $\{C,D\}$ and $\{E\}$.

Example 5. Why does swapping accepting states fail to complement an NFA?

An NFA accepts a string if at least one computation path reaches an accepting state. It rejects only when every path fails.

Swapping the accepting set produces a machine that accepts when at least one path reaches a state that was previously non-accepting.

Those two conditions are not complementary. A string with two paths — one reaching an old accepting state and one reaching an old non-accepting state — is accepted by both machines.

Concretely, take an NFA over $\{a\}$ with start state $p$ and transitions $\delta (p,a)=\{p,q\}$, with $q$ accepting. The string $a$ is accepted, since the path to $q$ succeeds.

Swap the accepting set so that $p$ accepts and $q$ does not. The string $a$ is still accepted, via the path staying at $p$.

Both machines accept $a$, so the second is not the complement of the first.

The correct procedure is to convert to a DFA first, where each string has exactly one path, and then swap. That is why complementation is described as easy for DFAs and expensive for NFAs — the subset construction in between can cost exponential blow-up.

Example 6. Prove that $L=\{a^n{b}^n:n\ge 0\}$ is not regular using Myhill-Nerode.

Consider the infinite family of strings $a^0,a^1,a^2,a^3,\dots$

Take any two distinct members $a^i$ and $a^j$ with $i\ne j$.

Append the suffix $b^i$.

Then $a^i{b}^i$ is in $L$, since the counts match. But $a^j{b}^i$ is not in $L$, since $j\ne i$.

So the suffix $b^i$ distinguishes the two strings, and this works for every distinct pair.

The strings $a^0,a^1,a^2,\dots$ are therefore pairwise inequivalent, giving infinitely many Myhill-Nerode equivalence classes.

By the theorem, a language is regular exactly when it has finitely many classes. This language has infinitely many, so it is not regular.

The intuition matches: recognising the language requires remembering how many $a$s were seen, which is unbounded, and a finite automaton has nowhere to keep that count.

Note that Myhill-Nerode gave a complete proof here in four lines, whereas the pumping lemma would require setting up a pumping length, choosing a witness string, and reasoning about every possible decomposition.

Summary

A finite automaton remembers only its current state, so a language is regular exactly when the strings read so far fall into finitely many interchangeable classes.

A DFA has exactly one transition per state and symbol; a missing transition means a dead state is required. Membership costs $O(n)$.

An NFA accepts if any path succeeds. NFAs and DFAs recognise the same languages, with the subset construction converting one to the other at a worst-case cost of $2^n$ states — a bound that is tight for the "$k$-th symbol from the end" family.

Regular expressions use union, concatenation and star, with star including the empty string and precedence running star, then concatenation, then union.

Kleene's theorem makes expressions and automata interchangeable, with Thompson's construction one way and state elimination the other.

Regular languages are closed under union, intersection, complement, concatenation, star, reversal and difference. Complementation requires a DFA, because swapping accepting states in an NFA does not complement the language.

Minimisation removes unreachable states, then merges equivalent ones by table filling, stopping only after a full pass marks nothing new.

Myhill-Nerode characterises regularity exactly: finitely many indistinguishability classes, and their count equals the minimal DFA's state count. Exhibiting infinitely many pairwise distinguishable strings proves non-regularity, often more cleanly than the pumping lemma.