Arden's theorem
Arden's theorem gives a method to solve simple linear equations over regular expressions (languages): the equation X = A X ∪ B has solution X = A* B, unique when A does not contain ε, and this is widely used to convert finite automata to regular expressions.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Arden's theorem is a short, algebraic tool used when converting finite automata (DFA/NFA/GNFA) to regular expressions. Engineers use it to derive a closed form (regular expression) for the language accepted by a state machine — for example, when simplifying control logic, writing lexical patterns, or proving equivalence between models.
Key ideas
- Regular expression: a symbolic description of a regular language built from symbols, union (∪), concatenation, and Kleene star (*) with ε (empty string) and Ø (empty language).
- Kleene star: For a language A, A* is the set of all finite concatenations of strings from A, including the empty string ε.
Statement (Arden's theorem / Arden's lemma):
- Consider the equation over languages (or regular expressions treated as language variables): X = A X ∪ B where A and B are known regular expressions (or languages) and X is the unknown language (regular expression) variable.
- Then the expression
X = A* Bis a solution. Moreover, if ε ∉ A (that is, A does not contain the empty string), then this solution is unique: the only language X satisfying the equation isA* B.
Notes and assumptions used in proofs and applications:
- Concatenation is not commutative:
A Bmeans strings from A followed by strings from B; order matters. - The identity
A* = ε ∪ A A*is used repeatedly. Proofs assume standard properties of Kleene star. - If ε ∈ A, then solutions may not be unique. In that case
A* Bis still a solution, but additional solutions can exist.
Proof that X = A* B is a solution:
- Start with
A X ∪ Band substituteX = A* B. A (A* B) ∪ B = (A A*) B ∪ B.- Use
A* = ε ∪ A A*to rewrite(A A*) ∪ {ε}asA*. - Thus
(A A*) B ∪ B = ( (A A*) ∪ {ε} ) B = A* B. - So
A (A* B) ∪ B = A* B, i.e.,X = A* Bsatisfies the equation.
Proof of uniqueness when ε ∉ A (sketch, standard induction-style argument):
- Let X be any language satisfying
X = A X ∪ B. - Take w ∈ X. Either w ∈ B (done), or w ∈ A X, so w = uv where u ∈ A and v ∈ X.
- Repeat the argument on v. Because ε ∉ A, each step consumes at least one symbol: you cannot loop forever without reducing string length. So after a finite k steps you reach vk ∈ B and w ∈ A^k B ⊆ A* B.
- Thus X ⊆ A* B.
- But
A* B ⊆ Xfollows from substitutingX = A* Binto the equation or by algebra:A* B = (ε ∪ A A*) B = B ∪ A (A* B) ⊆ B ∪ A X = X. - Therefore X = A* B; uniqueness holds.
What if ε ∈ A?
- Example: take A = {ε}, B = {a}. Equation becomes
X = {ε} X ∪ {a}which simplifies toX = X ∪ {a}. Any language X that containsais a solution. So solutions are not unique.
How Arden's theorem is used in automata → regular expression conversion:
- For each state i of an automaton create a variable R_i for the set of strings that take you from state i to some final state (or a set of final states). Write one equation per state describing its outgoing transitions: R_i = sum_over_transitions (symbol · R_j) ∪ (ε if state i is accepting)
- Solve the system from equations for states with no incoming dependencies or by elimination using Arden's theorem repeatedly until you get the expression for the start state.
What to draw in exam diagrams:
- Draw the automaton: circles for states, label start state with an incoming arrow, mark accepting (final) states with double circles, label transitions with symbols. When demonstrating elimination, re-draw small step graphs showing states removed and new direct transitions with the regular expression labels formed by concatenation and union.
Formulas
X = A X ∪ B — equation form where X is unknown, A,B regular expressions (or languages).
- A: regular expression (language) multiplying on the left of X. No unit.
- B: regular expression (language) added (union) to AX.
X = A* B — solution produced by Arden's theorem (valid for any A,B); unique when ε ∉ A. Also, the symmetric form: if the equation is X = X A ∪ B, then X = B A* is a solution; it is unique when ε ∉ A.
- Symbols: X, A, B are regular expressions (or languages);
εis the empty string;A*is Kleene star of A.
A* = ε ∪ A A* — Kleene star identity used in proofs.
- Applies for any regular expression A.
When applying to automata, the per-state equation syntax to remember:
R_i = (⋃_{i→j with symbol s} s · R_j) ∪ (ε if i is final)
- Here
s · R_jmeans symbol s concatenated with language R_j.
Worked examples
Example 1 (simple two-state DFA → regular expression): Automaton (draw this): two states q0 (start), q1 (final). Transitions: q0 --a--> q0, q0 --b--> q1, q1 --a--> q1, q1 --b--> q1. Set up equations for languages from state to a final state:
R0 = a R0 ∪ b R1(q0 is not final),R1 = (a ∪ b) R1 ∪ ε(q1 is final so ε present). Solve R1 first using Arden's theorem:R1 = (a ∪ b)* ε = (a ∪ b)*. Substitute into R0:R0 = a R0 ∪ b (a ∪ b)*. Apply Arden:R0 = a* b (a ∪ b)*. Answer: The language accepted from start q0 is(a)* b (a ∪ b)*(you may writea* b (a ∪ b)*).
Example 2 (apply uniqueness check):
Equation X = a X ∪ b. Since ε ∉ {a}, unique solution is X = a* b.
Check: Substitute a* b into RHS: a (a* b) ∪ b = (a a*) b ∪ b = (ε ∪ a a*) b = a* b.
Example 3 (non-unique case):
Equation X = {ε} X ∪ {a}. Since ε ∈ {ε}, solutions are any language that contains a. By Arden's theorem, {ε}* {a} = {a} is a particular solution (since {ε}* = {ε}), but not the only one: {a}, {a, b}, Σ* (if alphabet contains b) that contain a are also solutions. This shows non-uniqueness.
Common mistakes
- Not including ε for final states when setting up equations from automata.
- Applying Arden's theorem to an equation of the wrong shape (e.g.,
X = X A ∪ Brequires rewriting or, better, using the right-version: solution isX = B A*whenε ∉ A). - Failing to simplify union/concatenation expressions and producing needlessly complex regex.
For your exam
Types of questions you will see:
- Definitions: State Arden's theorem and explain conditions for uniqueness.
- Short notes: Show how Arden's theorem is used to convert DFA/NFA to regular expressions; draw and label the automaton.
- Derivations: Prove that
A* Bis a solution and prove uniqueness whenε ∉ A(describe the finite-descent argument). - Long questions: Given a small DFA/NFA, set up equations and solve them using Arden's theorem; draw intermediate elimination steps.
- Diagrams: You will be asked to draw automata and indicate equations per state.
What a full-marks answer includes:
- Clear statement of Arden's theorem and the uniqueness condition.
- Correct setup of equations from the automaton with ε for final states.
- Correct step-by-step application of Arden's theorem with justification (use
A* = ε ∪ A A*where needed). - Final regular expression simplified and a short correctness check (substitution or language reasoning).
Quick check
- State Arden's theorem in one line.
- Solve the equation
X = a X ∪ busing Arden's theorem. - If
X = A X ∪ Band ε ∈ A, is the solutionA* Bunique? Give a one-line reason. Answers: 1) X = A X ∪ B has solution X = A* B, unique if ε ∉ A. 2)X = a* b. 3) No — if ε ∈ A the solution need not be unique; counterexample A={ε}, B={a} gives many solutions.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?