Arden's rule
/ AR-dunz /
There is an algebraic alternative to drawing and erasing states: write the automaton as a system of equations about languages and solve it like high-school algebra. Arden's rule is the single trick that makes those equations solvable. It tells you how to untangle an equation where a language is defined partly in terms of itself, which happens whenever an automaton has a loop.
Set up one unknown per state: let X_i be the language of all strings that drive the automaton from state i to an accept state. Reading the transitions gives equations like X = AX + B, where A and B are known languages and the AX term reflects 'take an A-step and keep going'. Arden's rule says: if A does not contain the empty string ε, then the unique solution of X = AX + B is X = A*B. Intuitively, you must take zero or more A-steps (that is the A*) and then finish with a string in B. Solving the whole system, substituting solutions back, and reading off the equation for the start state gives a regular expression for the language.
Arden's rule is the backbone of the algebraic proof of Kleene's theorem's backward direction, an alternative to state elimination that some find cleaner because it is just equation-solving. The one condition to respect is the 'ε not in A' proviso: if A could match the empty string, the solution is no longer unique (A*B is still a solution, but so is A*(B + anything looping forever)), and the rule does not apply. With that caveat honored, Arden's rule and state elimination always give equivalent expressions, possibly written differently.
Solve X = aX + b with ε not in L(a): by Arden's rule X = a*b, meaning 'any number of a's then a b'. For a two-state loop you get a small system; substituting solutions back yields the start state's regular expression.
The fixpoint of X = AX + B is A*B, provided ε is not in A.
The condition ε not in A is essential: if A can match the empty string, X = AX + B has more than one solution and Arden's rule no longer pins down a unique answer.