Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 59 ยท Regular Expressions and Languages

From Finite Automata to Regular Expressions: Arden's Theorem and State Elimination

Learn Kleene's theorem and two methods for converting a finite automaton to a regular expression, Arden's theorem and state elimination, with Python code.

You can turn a regular expression into an automaton with Thompson's construction. This lesson does the opposite: given a DFA or NFA, produce a regular expression for its language. Together, the two directions prove Kleene's theorem.

Kleene's theorem. A language is regular (recognized by a finite automaton) if and only if it can be described by a regular expression.

So regular expressions, DFAs, NFAs and ฮต-NFAs all describe exactly the same class of languages. There are two classic methods for the automaton-to-expression direction: Arden's theorem (solve equations) and state elimination (shrink the graph). Both rely on the same idea: let the edges of the automaton carry regular expressions instead of single symbols.

Method 1: Arden's theorem

Arden's theorem. If P and Q are regular expressions and P does not contain ฮต, then the equation R = Q + RP has the unique solution R = QP*.

Read the equation as "R is either Q, or something in R followed by P". Unrolling it gives Q + QP + QPP + ..., which is QP*. The condition "P does not contain ฮต" is what makes the solution unique; without it, other solutions exist.

The recipe

  1. Write one equation per state: the language reaching that state. For each transition p --a--> q, add the term (language of p)ยทa to the equation of q. The start state's equation gets an extra ฮต.
  2. Solve the equations one by one. Whenever a state's equation refers to itself (R = Q + RP), apply Arden to remove the self-reference. Substitute the result into the others.
  3. The answer is the union of the expressions for all accepting states.

Worked example

Take the DFA for "even number of a's", with start state E (also accepting) and the other state O.

flowchart LR
    start(( )) --> E
    E((("E"))) -->|"a"| O(("O"))
    E -->|"b"| E
    O -->|"a"| E
    O -->|"b"| O

E = even number of a's so far, O = odd.

The equations (E = strings reaching E, O = strings reaching O):

TEXT
E = ฮต + E b + O a
O = E a + O b

Solve the second with Arden (R = O, Q = Ea, P = b): O = E a b*. Substitute into the first:

TEXT
E = ฮต + E b + E a b* a  =  ฮต + E (b + a b* a)

Arden again with Q = ฮต and P = b + ab*a: E = (b + ab*a)*. E is the only accepting state, so the language is (b + ab*a)*: any number of "b" or "a, some b's, then a" blocks. That is a correct and perhaps surprising description of "even number of a's". The code below checks it.

Python Verify an expression derived with Arden's theorem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Arden's method is quick for small DFAs by hand but gets messy for bigger ones, because the substitutions grow. A program prefers the second method.

Method 2: state elimination

Convert the automaton into a generalized NFA (an L-graph: a graph whose edges are labeled with regular expressions, not just symbols). Then remove states one at a time, patching up the paths that went through them, until only a start and an accept state remain. The label of the single remaining edge is the answer.

  1. Add a new start state with an ฮต-edge to the old start, and a new accept state with ฮต-edges from every old accepting state.
  2. To eliminate an internal state q: for every pair (p, r) with an edge p โ†’ q and an edge q โ†’ r, add (or union into the existing p โ†’ r edge) the label R(p,q) ยท R(q,q)* ยท R(q,r), where R(q,q) is q's self-loop label (if any).
  3. Remove q and repeat. When only the new start and accept state remain, the label on the edge between them is a regular expression for the language.
flowchart LR
    p(("p")) -->|"R1"| q(("q"))
    q -->|"R2 (loop)"| q
    q -->|"R3"| r(("r"))
    p -.->|"R1 R2* R3"| r

Eliminating q: the dotted edge is what replaces the path p, q, r.

Python State elimination: DFA to regular expression

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The elimination order determines how compact the result is; the program above removes states in list order and prints 1*00*1((0+11*0)0*1)*, which is longer and harder to read than the hand-simplified (0+1)*01. Both describe the same language, and the brute-force comparison confirms it. In practice you simplify using the identities from the previous lessons: R + R = R, ฮตR = R, (R*)* = R* and so on.

Which method to use

Situation Better method
Small DFA, by hand Arden's theorem
Writing a program State elimination
NFA with ฮต-moves Either; state elimination handles ฮต-edges directly
You only need to know if a language is regular Neither; build any automaton or expression

The length of the expression can grow exponentially with the number of states in the worst case, which is an inherent cost of the conversion, not a flaw in the method.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the solution of R = Q + RP when P does not contain ฮต?

    Unrolling gives Q + QP + QPP + ..., which is QP*. The condition that P lacks ฮต makes the solution unique.
  2. 2. In state elimination, how do you replace the path p โ†’ q โ†’ r when q has a self-loop L?

    The path may loop at q any number of times before moving on, so the loop label is starred and placed in the middle.
  3. 3. Kleene's theorem states that...

    Finite automata and regular expressions describe the same class of languages: the regular languages.
  4. 4. Why do we add a new start state and a new accept state before state elimination?

    A unique start and accept state with no extra arrows into the start or out of the accept state make elimination well-defined.

Summary

  • Kleene's theorem: finite automata and regular expressions are equivalent descriptions of the regular languages.
  • Arden's theorem solves R = Q + RP as R = QP* (P without ฮต), and gives a state-by-state equation method.
  • State elimination removes states from an expression-labeled graph (an L-graph), patching paths with R(p,q) R(q,q)* R(q,r).
  • Either method may produce long expressions; simplify with the regex identities.

Next: Closure Properties of Regular Languages