Kleene's algorithm

In theoretical computer science, in particular in formal language theory, Kleene's algorithm transforms a given deterministic finite automaton (DFA) into a regular expression. Together with other conversion algorithms, it establishes the equivalence of several description formats for regular languages.

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

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.

...
Wikipedia