◄ WORLD V · SONNY 5DART 181 · a helldive at the net

ARDEN’S RULE solve the automaton's equations; the answer is a regex

Write a finite automaton as a system of equations — each state’s language in terms of the states it reaches. One equation always has the shape X = AX + B (a self-loop A, an exit B). Arden’s rule solves it: the unique solution is X = A*B. Apply it state by state and the automaton collapses into a single regular expression — the constructive proof of the automaton→regex half of Kleene’s theorem.

THE TECHNIQUE X = AX + B => X = A*B

A two-state automaton for a*b: the start state loops on a and exits on b to the accept state, giving X = aX + b. Arden solves it to X = a*b — and the resulting regex accepts exactly the strings the automaton does. Verify the solution against the machine: live demo







  
HISTORY & CREDIT Dean Arden, 1961

  
“X = AX + B always has one solution.” — only if A does not contain the empty string. If ε ∈ A, then A*B is the smallest solution but not unique (you can add anything). Arden’s uniqueness needs the empty-word-free condition — the fine print that makes the rule sound. cited

  
1961 · Dean N. Arden — “Delayed logic and finite state machines”: the identity X = AX + B ⇒ X = A*B, now Arden’s rule/lemma.
role · it is the engine of state elimination — the standard algorithm converting any finite automaton to a regular expression, one Arden-substitution per state.
duality · it is the regular-language analogue of solving a linear recurrence: A* plays the role of 1/(1−A) in the algebra of languages.

  
That last analogy is exact: in the semiring of languages, A* = 1 + A + A² + … is the closure that stands in for (1−A)⁻¹ — Arden’s rule is the geometric series, read in languages instead of numbers. Arden 1961






  
RECOMMEND FOR I-13 the solved regex matches the machine

  
Arden solves X = aX + b to a*b; on the canonical compiler the automaton accepts exactly that language:

  
$ i13 run arden.i13   # X = aX + b  ->  X = a*b ; run the automaton on candidates
b   -> accept     ab  -> accept     aab -> accept     -- exactly a* b
aa  -> reject                                          -- no trailing b

  
Recommend: Arden’s rule is LIT and the automaton→regex engine for I-13 — verified that solving X = aX + b to a*b yields an automaton accepting exactly b, ab, aab, … and rejecting aa (checked on the canonical compiler). It is the constructive half of Kleene’s theorem (179): state-elimination by repeated Arden-substitution turns any I-13 transition table back into a regular expression. And it is a familiar shape in disguise — A* is the language-semiring’s 1/(1−A), so the whole method is the geometric series solved over languages instead of numbers.