Converting an automaton to a regular expression

Let’s see how to convert any finite automaton to a regular expression.

The algorithm

The input is some NFA A. First we turn it into a GNFA. In the second phase, in each step we remove one state, adjust the transition function accordingly and repeat until only two states remain: the start state and the accept state. There is an edge between them whose label is a regular expression, and this is the result of the whole algorithm. So the whole procedure consists mainly of removing a state and then repairing the automaton so that we obtain an equivalent one.

Removing one state

We can illustrate how to remove one state with a simple example. Suppose part of our automaton looks like this:

where R_i are some regular expressions. What would the automaton look like if we removed state q_r? We can think of it like this: we are in state q_i and ask which strings we can generate along this stretch. If we go from state q_i straight to state q_j, these are all the strings that match the regular expression R₄.

If we go to state q_r instead, we can generate strings of the form R₁. But in state q_r we can loop on the regular expression R₂, so we can in fact generate strings of the form $R_1\circ (R_2^{\ast })$. And since we can still get from state q_r to state q_j, we add the regular expression R₃ at the end. Altogether, this route gives us strings of the form $R_1\circ (R_2^{\ast })\circ R_3$.

Now we know that this part of the automaton can produce strings of the form R₄ or of the form $R_1\circ (R_2^{\ast })\circ R_3$. We can of course write this as a regular expression: $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Now we can simply remove state q_r, leaving just the two states q_i and q_j, and in place of R₄ we write the expression we have just worked out:

We carry out this procedure for every edge from every state q_i to some state q_j, including loops, that is, including the case where q_i = q_j.

After removing one state we get an equivalent automaton, that is, an automaton that recognises the same language.

The complete algorithm

The input is an NFA A = ⟨Q, Σ, δ, q₀, F⟩.

1. Convert the NFA A to a GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. From now on we write k for the number of states in Z.
2. If k = 2, the algorithm ends and the edge between the start state and the accept state carries the resulting regular expression.
3. If k>2, choose any state q_r that differs from the start and accept states, that is, q_r ≠ q₀′ and q_r ≠ q_f′. Then create a new GNFA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ for which the following holds: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ and for all q_i ∈ Q′′ ∖ {q_f′} and all q_j ∈ Q′′ ∖ {q₀′} let $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ where R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Then continue with step 2.

Example

Suppose the input is this finite automaton:

First we convert it to a GNFA (we won’t draw the unnecessary ∅-transitions):

Now we apply the second part of the algorithm and remove a node. We start with node q₂. We remove node q₂ and add a transition from state q₁ to state q_f. We label this transition b(a|b)^∗, because from node q₁ we get to state q₂ on strings of the form b, then we can loop on a|b, which gives us (a|b)^∗, and finally we move to q_f using the epsilon rule. Note that b(a|b)^∗ϵ = b(a|b)^∗. We get the automaton:

We still have to remove the last state, q₁. We add an edge from state q_s to state q_f. How do we label it? We get to state q₁ through an epsilon rule, which we can simply drop. Then we can loop on a, so we obtain the regular expression a^∗. And finally we follow the edge to q_f, so we concatenate the expression with b(a|b)^∗. We therefore label the edge with the regular expression a^∗ b(a|b)^∗.

The automaton now has only two states, so the algorithm ends. The edge carries the resulting regular expression.

Sources

• The example and the description of the algorithm come from M. Sipser: Introduction to the Theory of Computation