DFA to Regular Expression (State Elimination)

Kleene’s theorem, the other direction

Kleene’s theorem says finite automata and regular expressions describe exactly the same languages. The Regular Expressions lesson goes from a regex to an NFA (Thompson’s construction). This lesson goes the other way: from a DFA to a regular expression.

The idea: arrows labelled with regexes

Allow arrows to carry whole regular expressions instead of single symbols. Such a machine is called a generalized NFA (GNFA). Then remove the states one by one. Each time a state disappears, the arrows around it absorb what it did, so the language never changes. In the end only one arrow is left, and its label is the answer.

The algorithm

1. Add a new start state S with an ε-arrow to the old start, and a new final state F with ε-arrows from every accepting state. S has nothing coming in and F has nothing going out.
2. Merge parallel arrows with union: two arrows labelled a and b become one arrow a|b.
3. Eliminate the old states one at a time. For a state q with self-loop L (if there is no loop, L* = ε), replace every path p → q → r:

R(p, r)  ←  R(p, r) | R(p, q) L* R(q, r)

Read it as: go straight from p to r as before, or go to q, loop there any number of times, then go on to r. Then delete q. 4. When only S and F are left, the label of S → F is the regular expression.

Worked example: binary numbers divisible by 3

States r0, r1, r2 are the remainders mod 3. r0 is the start and the only accepting state. Eliminate in the order r2, r1, r0:

Step	What happens	New label
add S, F	S → r0 is ε, r0 → F is ε
eliminate r2	loop 1 becomes 1*; path r1 → r2 → r1	r1 loop = 01*0
eliminate r1	loop becomes (010); path r0 → r1 → r0	r0 loop = 0 ∣ 1(01*0)*1
eliminate r0	loop becomes (0∣1(01*0)1); path S → r0 → F	S → F = (0∣1(01*0)1)

The result is the famous (0|1(01*0)*1)*.

The order changes the look, not the language

Every order gives a correct answer, but some are much shorter. For the same DFA:

Order	Result
r2, r1, r0	(0|1(01*0)*1)*
r1, r2, r0	(0|11|10(1|00)*01)*
r0, r1, r2	0*|0*1(10*1)*10*|0*1(10*1)*0(1|0(10*1)*0)*0(10*1)*10*

All three describe the same set of strings. A good habit is to eliminate states with few arrows first, and to keep the start and accepting states for last.

Many textbooks write union as + instead of |, so the first answer becomes (0 + 1(01*0)1).

Another method: Arden’s theorem

Arden’s theorem: if P doesn’t contain ε, the equation R = Q + RP has the unique solution R = QP*.

Write one equation per state: “the strings that reach this state”. For even number of a’s (states E and O, E is the start and accepting):

E = ε + E b + O a
O = E a + O b

• Solve O with Arden (Q = Ea, P = b): O = E a b*.
• Substitute: E = ε + E b + E a b* a = ε + E (b + a b* a).
• Arden again: E = (b + aba).

E is the accepting state, so the language is (b|aba). That matches state elimination with the order O, E.

Code

def is_atom(r):
    """A single symbol, or one group like (a|b) or x*."""
    if len(r) == 1:
        return True
    if r.endswith('*'):
        return is_atom(r[:-1])
    if r[0] != '(':
        return False
    depth = 0
    for i, ch in enumerate(r):
        depth += (ch == '(') - (ch == ')')
        if depth == 0:
            return i == len(r) - 1      # the first '(' closes at the very end
    return False

def group(r):                           # brackets around a union inside a concatenation
    depth = 0
    for ch in r:
        depth += (ch == '(') - (ch == ')')
        if ch == '|' and depth == 0:
            return f'({r})'
    return r

def union(a, b):                        # None means ∅ (no arrow at all)
    if a is None or a == b: return b
    if b is None: return a
    return f'{a}|{b}'

def concat(*parts):                     # '' means ε
    if any(p is None for p in parts): return None
    return ''.join(group(p) for p in parts)

def star(r):
    if not r: return ''                 # ∅* = ε* = ε
    if r.endswith('*') and is_atom(r): return r
    return f'{r}*' if is_atom(r) else f'({r})*'

def dfa_to_regex(delta, start, accept, order):
    """State elimination. delta[p][symbol] = q."""
    R = {}
    for p in delta:
        for c, q in delta[p].items():
            R[p, q] = union(R.get((p, q)), c)
    R['S', start] = ''                  # new start, ε-arrow
    for f in accept:
        R[f, 'F'] = ''                  # new final, ε-arrows
    for q in order:
        loop = star(R.pop((q, q), None))
        ins = [(p, r) for (p, x), r in R.items() if x == q]
        outs = [(s, r) for (x, s), r in R.items() if x == q]
        for p, r_in in ins:
            for s, r_out in outs:
                R[p, s] = union(R.get((p, s)), concat(r_in, loop, r_out))
        R = {k: v for k, v in R.items() if q not in k}
    return R.get(('S', 'F'))

div3 = {'r0': {'0': 'r0', '1': 'r1'}, 'r1': {'0': 'r2', '1': 'r0'}, 'r2': {'0': 'r1', '1': 'r2'}}
print(dfa_to_regex(div3, 'r0', ['r0'], ['r2', 'r1', 'r0']))     # (0|1(01*0)*1)*

Each result was checked against its DFA on every string up to length 9.

Common mistakes

• Skipping S and F. If the old start state has incoming arrows, or there are several accepting states, the final answer gets lost.
• Overwriting an existing arrow. If p → r already exists, join it to the new path with |. Don’t replace it.
• Forgetting the loop. The middle part is L*, not L. With no loop it is ε, not ∅.
• Missing brackets. a|b followed by c is (a|b)c, not a|bc.
• Thinking different answers mean a mistake. Different elimination orders give equivalent expressions.