Kleene's algorithm

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

Algorithm description

According to ,^[1] the algorithm can be traced back to Kleene (1956).^[2]

This description follows Hopcroft and Ullman (1979).^[3]

Given a deterministic finite automaton M = (Q, Σ, δ, q₀, F), with Q = { q₀,...,q_n } its set of states, the algorithm computes the sets R^k
_ij of all strings that take M from state q_i to q_j without going though any state numbered higher than k. Both i and j may be higher than k, that is, "going through a state" means entering and leaving it. Each set R^k
_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 Rⁿ
_0j represents the set of all strings that take M from its start state q₀ to the final state q_j. If F = { q₁,...,q_f } is the set of accept states, the regular expression Rⁿ
₀₁ | ... | Rⁿ
_0f represents the language accepted by M.

References

1. Jonathan L. Gross and Jay Yellen, ed. (2004). Handbook of Graph Theory. Discrete Mathematics and it Applications. CRC Press. ISBN 1-58488-090-2. Here: sect.2.1, remark R13 on p.65
2. Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automate" (PDF). Automata Studies, Annals of Math. Studies. 34. Princeton Univ. Press.
3. John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Here: Theorem 2.4, p.33-34