What does Kleene's theorem say about the relationship between the three regular operators and finite automata?
answer
- an equivalence, so count the directions
- patterns and machines describe one class
- one construction each way
- fragments joined by empty-string transitions
- size stays linear in the pattern
basics
~20 sKleene's theorem says patterns and finite automata describe exactly the same languages, in both directions: every pattern built from concatenation, alternation and the star has an equivalent finite automaton, and every finite automaton has an equivalent pattern.
solid answer
~40 sThe theorem is an equivalence, and both halves matter. From a pattern to a machine, **Thompson construction** gives the recipe: each operator becomes a small fragment with one start state and one accept state, wired to its operands by empty-string transitions, so the machine's size stays linear in the pattern's size. From a machine back to a pattern, **state elimination** removes states one at a time, relabelling the remaining edges with patterns until a single edge carries the whole language. The payoff is that a pattern is not just notation: it is a description of a machine you can actually build, so questions about the pattern become questions you can answer by inspecting or running that machine.
code
pseudocode · 28 linesfunction build(node): # returns fragment(start, accept)
if node is symbol(c):
s = new state; f = new state
add transition s --c--> f
return fragment(s, f)
if node is concat(A, B):
a = build(A); b = build(B)
add transition a.accept --empty--> b.start
return fragment(a.start, b.accept)
if node is alt(A, B):
a = build(A); b = build(B)
s = new state; f = new state
add transition s --empty--> a.start
add transition s --empty--> b.start
add transition a.accept --empty--> f
add transition b.accept --empty--> f
return fragment(s, f)
if node is star(A):
a = build(A)
s = new state; f = new state
add transition s --empty--> a.start # enter the operand
add transition s --empty--> f # zero copies
add transition a.accept --empty--> a.start # repeat
add transition a.accept --empty--> f # exit
return fragment(s, f)go deeper
Remember the headline: a pattern and a finite automaton are two notations for the same thing, and there is a mechanical way to turn one into the other in each direction.
Sketch the construction from a pattern to a machine operator by operator, and say what its output looks like: nondeterministic, with empty-string joins and a size proportional to the pattern.
Use the equivalence as the justification for an operational claim — that a rule's cost can be bounded before input arrives — and say which rule features void that justification.
The theorem is the argument for restricting a configuration language's pattern syntax: what is provably inside the three operators carries a guarantee, and what is outside carries none at any price.
## The statement, in both directions **Kleene's theorem**: the languages described by patterns built from single symbols using concatenation, alternation and the Kleene star are exactly the languages accepted by finite automata. Two claims, not one: 1. **Pattern to machine.** For every pattern there is a finite automaton accepting precisely the texts the pattern describes. 2. **Machine to pattern.** For every finite automaton there is a pattern describing precisely the texts it accepts. The second direction is the one candidates forget, and dropping it turns an equivalence into a one-way translation. It is the direction that licenses the name *regular languages* for a single class with two notations rather than for two classes that happen to overlap. ## Thompson construction — the first direction, built The construction is recursive over the pattern's structure. Every sub-pattern becomes a **fragment** with exactly one start state and one accept state, and fragments are joined only by **empty-string transitions**, so an enclosing operator never has to look inside its operands. - **A single symbol** becomes two states with one transition between them labelled by that symbol. - **Concatenation** takes the two fragments and links the first's accept state to the second's start state with an empty-string transition. - **Alternation** adds a new start and a new accept, with empty-string transitions branching into both operands and merging out of them. - **The star** adds a new start and a new accept with four empty-string transitions: into the operand, straight to the accept (the zero-copy case), from the operand's accept back to its start (the repeat case), and from the operand's accept to the new accept (the exit case). Two properties fall out and are worth stating precisely: - The result is **nondeterministic** and keeps its empty-string transitions. Thompson construction does not produce a deterministic machine; turning it into one is a separate step with its own cost, and it is not what the theorem claims. - The machine's size is **linear in the pattern's size** — at most twice the number of symbols and operators in states. Worked example: `(a|b)*c` has three symbols and three operators. Each symbol fragment is 2 states (6 so far), the alternation adds 2 (8), the star adds 2 (10), and the concatenation adds none — 10 states against a bound of 12. ## State elimination — the other direction Going back is less famous and just as constructive. Allow each edge of the machine to be labelled not by a single symbol but by a whole pattern, then delete states one at a time. When a state is removed, every path that went in, possibly looped on it, and went out is replaced by one edge whose label concatenates the incoming label, the star of the loop label, and the outgoing label. Alternation merges parallel edges. Delete every state but a start and an accept, and the surviving label is a pattern for the whole language. The three operators show up here for a structural reason, not a stylistic one: entering-then-leaving is concatenation, a self-loop is repetition, and two routes between the same pair of states are a choice. They are exactly the operations you need to summarise paths through a graph. ## What the equivalence buys an engineer | Question about a pattern | Answered by | |---|---| | Does it match anything at all? | reachability of an accept state in the built machine | | Does this text match? | running the machine over the text | | Do two rules describe the same set? | comparing the machines rather than the notation | | Can it be checked without unbounded work per symbol? | the machine exists, so a bound follows from its size | The last row is the one with operational weight. When a rule in a configuration file is *provably* a pattern over the three operators, it stands for a machine whose shape is known before any input arrives — which is what makes a claim about worst-case behaviour possible at all. When a rule uses a feature outside the three operators, that guarantee is not merely hard to obtain; the theorem simply does not apply to it. ## What an interviewer is listening for Both directions stated, the construction named and sketched, and the two properties of its output: nondeterministic with empty-string transitions, and linear in size. A candidate who adds that determinising afterwards is a separate step — and that the equivalence is what makes any claim about a rule's cost meaningful — is reasoning about why the theorem is useful rather than reciting it.
- In Thompson construction, where does the star's zero-copy case come from?From one specific edge: the fragment's new start state has an empty-string transition straight to its new accept state, bypassing the operand entirely. The other three edges enter the operand, loop from its accept back to its start, and leave it. Remove the bypass edge and you have built the one-or-more form instead.
- What proves the direction from a machine back to a pattern?State elimination. Let edges carry whole patterns as labels, then delete states one by one, replacing each removed state's in-loop-out paths with a single edge labelled by concatenation of the incoming label, the star of the loop, and the outgoing label; parallel edges merge by alternation. What survives is a pattern for the machine's language.
- Does Thompson construction produce a deterministic machine?No. Its output is nondeterministic and full of empty-string transitions — that is exactly what lets each operator wire its operands together without inspecting them. Making the machine deterministic is a separate construction with its own cost, and the theorem's claim holds without it.
saying these in an interview costs you the question
- States the equivalence in only one direction.
- Says Thompson construction outputs a deterministic machine.
- Claims the built machine's size grows exponentially with the pattern.
- Thinks the construction removes empty-string transitions as it goes.
- Assumes the equivalence still holds once non-regular features are added.