Chapter 13 of 34

Finite Automata to Regular Expression (Arden's Theorem)

Suppose someone hands you a DFA and asks, "What does this machine accept?" You can trace a few strings and guess, but a guess is not an answer. What you want is a regular expression that describes the machine's language exactly, derived by a method that cannot go wrong.

In Regular Expression to Finite Automata we turned regular expressions into automata. This chapter goes the other way and completes Kleene's theorem:

For every finite automaton M there is a regular expression R with L(R) = L(M). Two standard ways to find R are the state elimination method and the algebraic method based on Arden's theorem.

Both methods are mechanical and both appear regularly in university exams and GATE. Every expression derived in this chapter was checked against its automaton by simulation on all strings up to length 10 (12 for the binary examples).


The Big Idea

An automaton's language is the set of labels of all paths from the start state to an accepting state. With loops, there are infinitely many such paths. Both methods tame this infinity in the same way: a loop becomes a star.

  • State elimination removes states one by one, relabelling arrows with regular expressions, until only a single arrow from start to finish remains. It is a picture-based method.

  • Arden's method writes one equation per state and solves the system like simultaneous equations in algebra. It is a pen-and-paper method.


Method 1: State Elimination

We allow arrows to be labelled with whole regular expressions (such a machine is sometimes called a generalised NFA). Then:

Step 0: prepare the machine

  1. If the start state has any incoming arrow, add a new start state s with an ε-arrow to the old start.

  2. If there is more than one accepting state, or an accepting state has outgoing arrows, add a new single accepting state f with ε-arrows from every old accepting state (which stop being accepting).

  3. Merge parallel arrows: two arrows p –a→ q and p –b→ q become one arrow p –(a + b)→ q.

Step 1: eliminate states one at a time

To eliminate a state q (not s or f), look at every pair of a predecessor p and successor r of q:

          R1           R3
     p --------> q --------> r          becomes      p --( R4 + R1 R2* R3 )--> r
                 ↻ R2
     p ---------- R4 ---------> r   (existing direct arrow, if any; ∅ if none)

Why it works: any path from p to r that passes through q enters with R1, loops at q any number of times (R2*) and leaves with R3. The new label covers those paths plus the old direct arrow R4. Do this for every (p, r) pair, including p = r (which creates or updates a self-loop on p).

Step 2: read off the answer

When only s and f remain, the label on the arrow s → f is the regular expression.

Example 1: strings ending with a

State

a

b

→ q1

q2

q1

* q2

q2

q1

q1 has incoming arrows and q2 has outgoing arrows, so add s –ε→ q1 and q2 –ε→ f.

Eliminate q1   (self-loop b; predecessors s (ε) and q2 (b); successor q2 (a))
   s  → q2 :  ε b* a           = b*a
   q2 → q2 :  a + b b* a                (old self-loop a, plus the detour through q1)

Eliminate q2   (self-loop a + bb*a; predecessor s; successor f)
   s  → f  :  b*a (a + bb*a)* ε = b*a(a + bb*a)*

The result b*a(a + bb*a)* looks nothing like the obvious (a + b)*a, but they are equal: both mean "ends with a". This is normal: different methods and orders give different-looking but equivalent expressions.

Example 2: binary numbers divisible by 3

The state is the remainder so far. Reading bit x turns value v into 2v + x, so remainder r goes to (2r + x) mod 3.

State (remainder)

0

1

→ * q0

q0

q1

q1

q2

q0

q2

q1

q2

q0 is both start and accepting and has loops, so add s –ε→ q0 and q0 –ε→ f.

Order A: eliminate q2 first
   q2: self-loop 1, in from q1 (0), out to q1 (0)
   q1 → q1 :  0 1* 0
   then eliminate q1: self-loop 01*0, in from q0 (1), out to q0 (1)
   q0 → q0 :  0 + 1 (01*0)* 1
   then eliminate q0:  s → f = ( 0 + 1(01*0)*1 )*

Order B: eliminate q1 first (q1 has no self-loop)
   q0 → q0 : 0 + 11        q0 → q2 : 10
   q2 → q0 : 01            q2 → q2 : 1 + 00
   then eliminate q2:  q0 → q0 = 0 + 11 + 10(1 + 00)*01
   then eliminate q0:  s → f = ( 0 + 11 + 10(1 + 00)*01 )*

Order A gives the famous (0 + 1(01*0)*1)* from Regular Expressions. Order B gives a different expression; the program confirmed both accept exactly the multiples of 3 (and ε) among all binary strings up to length 12.


Arden's Theorem

The algebraic method rests on one result about equations whose unknown is a language.

Arden's Theorem: Let P and Q be regular expressions over Σ, where P does not contain ε (ε ∉ L(P)). Then the equation R = Q + RP has exactly one solution, R = QP*.

Intuition. Read R = Q + RP as "a string of R is either a string of Q, or a string of R followed by a string of P". Unwind it: a string of R is a string of Q followed by any number of P's. That is QP*.

Proof

(1) QP* is a solution. Substitute R = QP* into the right-hand side:

Q + (QP*)P  =  Q(ε + P*P)  =  QP*          using ε + P*P = P*

(2) It is the only solution. Let R be any language with R = Q + RP. Substitute the equation into itself k times:

R = Q + RP
  = Q + (Q + RP)P            = Q + QP + RP²
  = Q + QP + QP² + RP³
  ...
  = Q(ε + P + P² + … + P^k) + RP^(k+1)          for every k ≥ 0
  • QP* ⊆ R: the last line shows QPi ⊆ R for every i, so their union QP* ⊆ R.

  • R ⊆ QP*: take any w ∈ R and let k = |w|. Because ε ∉ P, every string in P has length at least 1, so every string in RPk+1 has length at least k + 1 > |w|. So w ∉ RPk+1, which forces w ∈ Q(ε + P + … + Pk) ⊆ QP*.

Hence R = QP*. ∎

Why the condition ε ∉ P matters

If P = ε, the equation becomes R = Q + R, which is true for every R that contains Q. For example with Q = a, both R = a and R = (a + b)* satisfy it. The solution is no longer unique, so the method could give a wrong answer. In equations built from a DFA or an ε-free NFA this never happens, since every arrow reads exactly one symbol.


Method 2: Solving Equations with Arden's Theorem

Setting up the equations

Assume the automaton has no ε-moves. For each state qi, let qi also stand for the set of strings that lead from the start state to qi. Then:

q_i  =  Σ ( q_j a )   over every arrow  q_j --a--> q_i     (+ ε  if q_i is the start state)

In words: to reach qi, either do nothing (only for the start state) or reach some predecessor qj and then read the symbol on its arrow. The answer is the sum of the expressions of the accepting states.

Then solve: substitute equations into each other, and whenever an equation has the form q = Q + qP (q appears on both sides, at the right end), apply Arden to get q = QP*.

Example 3: strings ending with a (Example 1 again)

q1 = ε + q1 b + q2 b          (start state; arrows into q1: from q1 on b, from q2 on b)
q2 = q1 a + q2 a              (arrows into q2: from q1 on a, from q2 on a)

Solve q2:   q2 = q1 a + q2 a     Arden (Q = q1 a, P = a)       =>  q2 = q1 a a*
Into q1:    q1 = ε + q1 b + q1 a a* b = ε + q1 (b + aa*b)
            Arden (Q = ε, P = b + aa*b)                         =>  q1 = (b + aa*b)*
So          q2 = (b + aa*b)* aa*

Answer (q2 is the only accepting state):  (b + aa*b)* aa*

Yet another form of "ends with a", again verified by the program.

Example 4: contains aa, and its complement

State

a

b

Meaning

→ q1

q2

q1

no aa yet, last symbol not a

q2

q3

q1

no aa yet, last symbol a

* q3

q3

q3

aa seen

q1 = ε + q1 b + q2 b
q2 = q1 a
q3 = q2 a + q3 a + q3 b

Substitute q2 into q1:   q1 = ε + q1 b + q1 ab = ε + q1 (b + ab)   =>  q1 = (b + ab)*
Then                     q2 = (b + ab)* a
q3 = (b + ab)* aa + q3 (a + b)                                     =>  q3 = (b + ab)* aa (a + b)*

Answer:  (b + ab)* aa (a + b)*

Now the bonus: if we make q1 and q2 the accepting states instead, the same DFA accepts "no two consecutive a's", and the answer is the sum of their expressions:

q1 + q2 = (b + ab)* + (b + ab)* a = (b + ab)* (ε + a)

which is exactly the expression we wrote by hand in Regular Expressions, Problem 5.

Example 5: binary numbers divisible by 3 with Arden

q0 = ε + q0 0 + q1 1
q1 = q0 1 + q2 0
q2 = q1 0 + q2 1

q2:  Arden (Q = q1 0, P = 1)                    =>  q2 = q1 0 1*
q1 = q0 1 + q1 0 1* 0      Arden (P = 01*0)     =>  q1 = q0 1 (01*0)*
q0 = ε + q0 0 + q0 1(01*0)*1 = ε + q0 (0 + 1(01*0)*1)
                                               =>  q0 = (0 + 1(01*0)*1)*

Answer (q0 accepting):  (0 + 1(01*0)*1)*

Same as Order A of state elimination: the algebra and the pictures are doing the same thing.

Example 6: it works for NFAs too

NFA for "ends with ab": q0 loops on a and b, q0 –a→ q1, q1 –b→ q2, accepting q2.

q0 = ε + q0 a + q0 b = ε + q0 (a + b)   =>  q0 = (a + b)*
q1 = q0 a                              =  (a + b)* a
q2 = q1 b                              =  (a + b)* ab          (answer)

Nondeterminism is no problem: the equations just collect all incoming arrows. Only ε-arrows must be removed first (see Epsilon-NFA & Epsilon-Closure).


The Other Form of Arden's Rule

Some books write the equations the other way round: qi stands for the strings that lead from qi to acceptance, using outgoing arrows:

q_i  =  Σ ( a q_j )  over every arrow  q_i --a--> q_j        (+ ε  if q_i is accepting)
Rule:   X = PX + Q  (ε ∉ P)   has the unique solution   X = P*Q
Answer: the expression of the START state

For the "contains aa" DFA of Example 4:

q3 = a q3 + b q3 + ε = (a + b) q3 + ε     =>  q3 = (a + b)*
q2 = a q3 + b q1
q1 = a q2 + b q1 = a a q3 + a b q1 + b q1 = (ab + b) q1 + aa(a + b)*
                                          =>  q1 = (ab + b)* aa (a + b)*

Same answer. The rule to remember: the star goes on the side where P is. R = Q + RP gives QP*; X = PX + Q gives P*Q. This outgoing form is exactly a right-linear grammar in disguise, as you will see in Regular Grammars.


Comparing the Two Methods

State elimination

Arden's method

Style

graphical, rewrite arrows

algebraic, solve equations

Handles ε-arrows

yes (label them ε)

remove them first (needs ε ∉ P)

Multiple accepting states

add a single new f

add the final-state expressions

Choice that affects the shape of the answer

order of elimination

order of substitution

Best for

small machines, pictures

exam answers with clear working

Both can produce expressions that grow very large for big automata (exponential in the worst case), so in practice you choose an elimination order that removes states with few connections first.


Common Mistakes

  • Writing R = PQ* or P*Q in the incoming form. For R = Q + RP the answer is QP*: Q comes first, because the string starts with a Q part.

  • Forgetting the ε on the start state's equation. Without it, every equation is homogeneous and the solution is ∅.

  • Mixing incoming and outgoing forms in one problem. Pick one form and use its matching rule.

  • Applying Arden when ε ∈ P (for example if ε-moves were left in). Remove ε-moves first.

  • Forgetting some predecessor/successor pairs in state elimination, especially the p = r case that creates a self-loop.

  • Only taking one accepting state when there are several. The answer is the sum over all accepting states.

  • Thinking a different-looking answer is wrong. Many correct expressions exist. Check by testing short strings or by converting both to minimal DFAs.


GATE-Style Questions

Q1. Solve R = b + Ra (the alphabet is {a, b}).

Here Q = b and P = a (ε ∉ P), so by Arden R = ba*: a b followed by any number of a's.

Q2. Solve X = aX + b.

This is the outgoing form X = PX + Q with P = a, Q = b, so X = a*b.

Q3. A DFA has start state q1 (accepting) and state q2, with q1 –a→ q2, q1 –b→ q1, q2 –a→ q1, q2 –b→ q2. Find a regular expression for its language.

q1 = ε + q1 b + q2 a, q2 = q1 a + q2 b. From the second, q2 = q1 ab*. Then q1 = ε + q1(b + ab*a), so q1 = (b + ab*a)*. This is the language of strings with an even number of a's.

Q4. Does R = a + R(ε + b) have a unique solution?

No. P = ε + b contains ε, so Arden's theorem does not apply. Indeed, ab* is a solution, but so is (a + b)*, which also equals a + (a + b)*(ε + b).

Q5. Eliminating the states of a DFA in two different orders gives two different regular expressions. What can you conclude?

Nothing is wrong: both expressions denote the same language (the language of the DFA). Regular expressions are not unique. Order A and Order B for the divisible-by-3 DFA are an example.


Summary

  • Every finite automaton has an equivalent regular expression, completing Kleene's theorem: regular expressions, DFAs, NFAs and ε-NFAs all define the same class of languages.

  • State elimination: add a fresh start and final state, then remove states, replacing every path p → q → r with R4 + R1R2*R3.

  • Arden's theorem: if ε ∉ P, then R = Q + RP has the unique solution R = QP* (and X = PX + Q has X = P*Q).

  • Arden's method: one equation per state from incoming arrows, ε added for the start state; solve by substitution; answer = sum over accepting states.

  • Different orders give different but equivalent expressions, e.g. (0 + 1(01*0)*1)* and (0 + 11 + 10(1 + 00)*01)* for binary multiples of 3.