Arden's Theorem & FA → RE Conversion¶

Arden's Theorem¶

Arden's Theorem is the algebraic tool for converting a finite automaton into an equivalent regular expression.

Statement¶

Let P and Q be regular expressions over alphabet Σ, and suppose ε ∉ L(P) (i.e., P does not describe the empty string). Then the equation:

R = Q + R · P

has a unique solution:

R = Q · P*

Verification¶

Substitute R = Q · P* back:

Q · P*  =  Q + (Q · P*) · P
       =  Q + Q · P* · P
       =  Q · (ε + P* · P)
       =  Q · P*              ✓   (since ε + P* · P = P*)

The condition ε ∉ L(P) is necessary

If P could generate ε, the equation may have multiple solutions and Arden's theorem does not give the unique one. In practice, when applying the theorem to DFAs with self-loops, you need to ensure the loop pattern P does not include ε.

FA → RE Conversion Method¶

The Setup¶

Every DFA can be described by a system of linear regular equations — one per state. For each state qᵢ, write an equation of the form:

qᵢ = (sum of terms: some_regex · qⱼ for each transition into qᵢ) + (ε if qᵢ is the start state)

Wait — it is cleaner to write equations from the source perspective. For each state qᵢ, the equation captures "how do you reach qᵢ?":

Think of qᵢ as a variable representing the set of strings that take the DFA from the start state to state qᵢ. Then:

The start state q₀ always includes ε (the empty string takes you from q₀ to q₀).
For each transition δ(qⱼ, a) = qᵢ, add the term qⱼ · a to the equation for qᵢ.

The language of the DFA is the union of all qᵢ for which qᵢ ∈ F.

Solving the System¶

Apply Arden's theorem to eliminate state variables one by one (starting from states that appear only in their own equation), until you have a closed-form regex for the accept states.

Worked Example¶

The DFA¶

A DFA that accepts all strings over {a, b} of the form (b | aa | abb | abaa)* · aba.

(This is taken from the lecture notes. Four states: q₀ is start and the only accept state is q₃.)

The transitions are:

δ(q₀, a) = q₁,   δ(q₀, b) = q₀
δ(q₁, a) = q₁,   δ(q₁, b) = q₂
δ(q₂, a) = q₃,   δ(q₂, b) = q₀
δ(q₃, a) = q₁,   δ(q₃, b) = q₀

Accept state: q₃.

Step 1: Write the Linear Equations¶

For each state, the variable represents "strings that take the DFA from the start to this state":

(1)  q₀ = ε + q₀·b + q₂·b + q₃·b
(2)  q₁ = q₀·a + q₁·a + q₃·a
(3)  q₂ = q₁·b
(4)  q₃ = q₂·a

(Explanation: q₀ includes ε because it is the start state; it also receives transitions from itself on b, from q₂ on b, and from q₃ on b. Similarly for the others.)

Step 2: Substitute to Reduce¶

Use equations (3) and (4) to eliminate q₂ and q₃ from equation (1):

From (3): q₂ = q₁·b
From (4): q₃ = q₂·a = q₁·b·a

Substitute into (1):

q₀ = ε + q₀·b + (q₁·b)·b + (q₁·b·a)·b
   = ε + q₀·b + q₁·bb + q₁·bab
   = ε + q₀·b + q₁·(bb + bab)

Use equation (2) to find q₁. From (2), apply Arden's theorem (since q₁ appears on both sides with pattern P = a):

q₁ = q₀·a + q₁·a + q₃·a
   = (q₀·a + q₃·a) + q₁·a

Here P = a, Q = q₀·a + q₃·a. So q₁ = (q₀·a + q₁·b·a·a)·a*. This gets complex. Let us follow the textbook's approach instead (substituting directly into q₀'s equation):

From (2): q₁ = (q₀·a + q₃·a) · a* = (q₀ + q₃)·a·a* — but q₃ = q₁·ba, so:

A cleaner path is to substitute everything into the q₀ equation and use Arden's once at the end.

Substituting q₁ = q₀·a, q₂ = q₀·ab, q₃ = q₀·aba (as first-order approximations, ignoring self-loops on q₁ first):

q₀ = ε + q₀·b + q₀·a·bb + q₀·a·bab + q₀·a·ba·a + …

The full derivation (as in the slides) groups these into:

q₀ = ε + q₀·(b + aa + abb + abaa)

This is in Arden form R = Q + R·P with Q = ε, P = (b + aa + abb + abaa).

Solution: q₀ = ε · (b + aa + abb + abaa)* = (b + aa + abb + abaa)* ... (5)

Step 3: Find the Accept State Regex¶

q₁ = q₀·a           = (b + aa + abb + abaa)*·a      ... from (3) of step 2
q₂ = q₁·b           = (b + aa + abb + abaa)*·ab     ... (6)
q₃ = q₂·a           = (b + aa + abb + abaa)*·aba    ... (7)

Result¶

The regular expression for this DFA is:

(b + aa + abb + abaa)*·aba

Reading the result

This says: "Any number of repetitions of strings in {b, aa, abb, abaa}, followed by aba." The suffix aba is what triggers the accept state q₃.

Summary: Method for FA → RE via Arden's Theorem¶

Label each state q₀, q₁, …, qₙ as a variable.
Write a linear regular equation for each state:
Include ε for the start state.
For each incoming transition δ(qⱼ, a) = qᵢ, add qⱼ·a to the right-hand side of qᵢ's equation.
Solve the system by substitution, applying Arden's theorem whenever a variable appears on both sides.
The final regex for the language is the union of the solved expressions for all accept states.