From a Finite Automaton to a Regular Expression: Arden's Theorem and State Elimination

The mirror form, used when the equations are written the other way round:

Method 1: the equation method

The procedure.

1. For each state q write an unknown X for the set of strings taking the machine from the start state to q.
2. Write one equation per state: X for q equals the sum, over every transition into q, of the expression for the

source state concatenated with the symbol on that transition. For the start state, add epsilon, because the empty string reaches it.

1. Solve the system by substitution, using Arden's rule whenever an unknown appears on both sides.
2. The answer is the sum of the expressions for the final states.

Step 2 is where the direction has to be watched. The equation for q is about arrows into q, not out of it. A student who writes the equations from the outgoing arrows has written a different and wrong system.

Worked, in full

Take the machine for the strings over {a, b} ending in ab.

Accepts: ab, aab, bab, abab, bbab

Rejects: ε, a, b, ba, abb, aa

Step 1 and 2. The equations. Write X0, X1, X2 for the three states, and read off the arrows into each.

Into s0: from s0 on b, and from s2 on b. And s0 is the start state, so epsilon is added.

Into s1: from s0 on a, from s1 on a, and from s2 on a.

Into s2: from s1 on b, and nothing else.

Step 3. Solve. Take them in the easiest order, which is the one with the fewest unknowns on the right.

The third equation gives X2 directly in terms of X1, so substitute it into the second:

The second line factors X1 out by identity 6 read right to left. Now X1 appears on both sides in the mirror form, so Arden's rule gives

Substitute that into the first equation, remembering that X2 is X1 b:

Arden's rule again, in the mirror form with S equal to epsilon:

and then working back:

Step 4. The answer is X2, because s2 is the only final state.

(b + a (a + b a)* b b)* a (a + b a)* b

The checker decides that equality exactly, so the solution is right and not merely plausible. And the two intermediate expressions are right too, which is worth checking separately because an error in X0 or X1 would usually still give a plausible looking X2.

(b + a (a + b a)* b b)*

(b + a (a + b a)* b b)* a (a + b a)*

Accepts: ε, b, abb, bb, babb

Rejects: a, ab, aab, ba, aa

Accepts: a, aa, ba, aba, abba

Rejects: ε, b, ab, bb, abb

P5 and P6 are the same machine with a different final state, so their languages are exactly the sets X0 and X1 were defined to be. Both expressions check out, so the whole solution is verified and not just its last line.

And the answer is not the shortest one. The machine plainly accepts (a + b)* a b, and so:

(a + b)* a b

Both expressions are correct. Arden's method is mechanical and gives something correct; chapter 32's identities are what get it down to something short, and an examiner will accept either.

Method 2: state elimination

Often quicker by hand, and it is the method to use when the machine has more than three or four states.

The idea. Allow the arrows of the machine to carry whole regular expressions rather than single symbols. Then a state can be deleted by replacing every path through it with a single arrow carrying the expression for those paths.

The procedure.

1. Add a new start state with an empty arrow to the old start state, and a new single final state with empty

arrows from every old final state. Neither new state is ever deleted. This is chapter 34's invariant again, and it is needed for the same reason.

1. Pick any state other than the two new ones and delete it. For every pair of a state p with an arrow in and a

state q with an arrow out, replace those by a single arrow from p to q carrying

where the loop's star is epsilon if the deleted state has no loop. Where p already had an arrow to q, the two expressions are joined with a plus.

1. Repeat until only the two new states remain.
2. The single arrow between them carries the answer.

Worked, on the same machine

Take P1 again, and add the new start N and the new final F.

Arrows at the start. N to s0 on epsilon. s0 to s0 on b, s0 to s1 on a. s1 to s1 on a, s1 to s2 on b. s2 to s0 on b, s2 to s1 on a. s2 to F on epsilon.

Delete s1. Arrows in: from s0 on a, from s2 on a. Arrows out: to s2 on b. The loop on s1 is a, so its star is a star.

• s0 to s2 gains a a star b.
• s2 to s2 gains a a star b.

Now the arrows are: N to s0 on epsilon; s0 to s0 on b; s0 to s2 on a a star b; s2 to s0 on b; s2 to s2 on a a star b; s2 to F on epsilon.

Delete s0. Arrows in: from N on epsilon, from s2 on b. Arrows out: to s2 on a a star b. Loop on s0 is b, so its star is b star.

• N to s2 gains b star a a star b.
• s2 to s2 gains b b star a a star b, joined with the a a star b it already had.

Now: N to s2 on b star a a star b; s2 to s2 on a a star b + b b star a a star b; s2 to F on epsilon.

Delete s2. Arrows in: from N. Arrows out: to F. The loop on s2 is the union just written, so:

• N to F gains b star a a star b ( a a star b + b b star a a star b ) star.

The answer:

b* a a* b (a a* b + b b* a a* b)*

A third correct expression for the same language, arrived at by a different route, and checked. Which of P2, P7 and P8 a student produces depends on the method and the order of elimination, and all three earn the marks.

The order matters for length, not for correctness. Deleting the most connected state last usually gives the shortest answer, and deleting in a different order here gives a different expression for the same language.

Distinctions

What it does NOT mean

Arden's rule does not need the machine to be deterministic. The equations can be written for any finite automaton, and an NFA gives a union of terms on the right hand side.

The equation for a state is not about its outgoing arrows. It is about the arrows into it. This is the error that produces a system with a plausible solution and the wrong language.

Epsilon is added only to the start state's equation. Adding it elsewhere claims the empty string reaches that state, which it does not.

The answer is not unique. Three correct expressions for one machine appear above. Only the language is determined.

Arden's condition is not a formality. Without epsilon being absent from R, the equation has many solutions and the rule picks the smallest, which may not be the one the machine denotes.

Quick revision

• Arden's theorem: X equals RX plus S has the unique solution R star S when the language of R excludes epsilon.

The mirror form X equals XR plus S has S R star.

• The uniqueness proof: substitute repeatedly, and use the fact that every string of R to the m has length at

least m, which is exactly what the condition guarantees.

• Equation method: one unknown per state, one equation per state written from the arrows IN, epsilon added to the

start state's equation, solved by substitution and Arden. The answer is the sum over the final states.

• State elimination: add a new start and a new single final state, then delete states one at a time, replacing

paths through a deleted state by an arrow carrying in, loop starred, out; join parallel arrows with a plus.

• Both methods give correct expressions, usually different ones, and neither gives the shortest.
• Chapter 32's identities are what shorten the answer.

Test yourself

1. State Arden's theorem, both forms, with the condition. If the language of R does not contain epsilon, then X equals RX plus S has the unique solution R star S, and X equals XR plus S has the unique solution S R star.

2. Prove that R star S satisfies X equals RX plus S. Substitute: R R star S plus S is R plus S plus S, which is (R plus plus epsilon) S by distribution, which is R star S by identity 9.

3. Why does the uniqueness proof need epsilon to be absent from R? Because it relies on every string of R to the m having length at least m, so that for large enough n the term R to the n plus one X cannot contribute a string of a given length. If R contained epsilon that bound fails and the equation has many solutions.

4. In the equation method, which arrows does a state's equation use, and what extra term does the start state get? The arrows INTO that state, each contributing the source state's unknown concatenated with the transition's symbol. The start state's equation gains an epsilon term, because the empty string reaches it.

5. In state elimination, what expression replaces the paths through a deleted state? The expression on the incoming arrow, then the loop on the deleted state starred, then the expression on the outgoing arrow. Parallel arrows between the same pair are joined with a plus.

6. Two students produce different expressions for the same machine. Are both wrong? Neither need be. The language is determined but the expression is not, and the chapter gives three correct expressions for one machine, from Arden, from inspection and from state elimination.