Kleene's algorithm

Algorithm description

According to Gross and Yellen (2004), the algorithm can be traced back to Kleene (1956).

This description follows Hopcroft and Ullman (1979). Given a deterministic finite automaton M = (Q, Σ, δ, q₀, F), with Q = { q₀,...,q_n } its set of states, the algorithm computes

the sets Rk
ij of all strings that take M from state q_i to q_j without going through any state numbered higher than k.

Here, "going through a state" means entering and leaving it, so both i and j may be higher than k, but no intermediate state may. Each set Rk
ij is represented by a regular expression; the algorithm computes them step by step for k = -1, 0, ..., n. Since there is no state numbered higher than n, the regular expression Rn
0j represents the set of all strings that take M from its start state q₀ to q_j. If F = { q₁,...,q_f } is the set of accept states, the regular expression Rn
01 | ... | Rn
0f represents the language accepted by M.

The initial regular expressions, for k = -1, are computed as

R−1
ij = a₁ | ... | a_m       if i≠j, where δ(q_i,a₁) = ... = δ(q_i,a_m) = q_jR−1
ij = a₁ | ... | a_m | ε, if i=j, where δ(q_i,a₁) = ... = δ(q_i,a_m) = q_j

After that, in each step the expressions Rk
ij are computed from the previous ones by

Rk
ij = Rk-1
ik (Rk-1
kk)^* Rk-1
kj | Rk-1
ij

Example

The automaton shown in the picture can be described as M = (Q, Σ, δ, q₀, F) with

the set of states Q = { q₀, q₁, q₂ },

the input alphabet Σ = { a, b },

the transition function δ with δ(q₀,a)=q₀,   δ(q₀,b)=q₁,   δ(q₁,a)=q₂,   δ(q₁,b)=q₁,   δ(q₂,a)=q₁, and δ(q₂,b)=q₁,

the start state q₀, and

set of accept states F = { q₁ }.

Kleene's algorithm computes the initial regular expressions as

After that, the Rk
ij are computed from the Rk-1
ij step by step for k = 0, 1, 2. Kleene algebra equalities are used to simplify the regular expressions as much as possible.

Step 0:

Step 1:

Step 2:

((step 2 simplification to be completed))

Since q₀ is the start state and q₁ is the only accept state, the regular expression R2
01 denotes the set of all strings accepted by the automaton.