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 Gross and Yellen (2004),^[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.

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 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 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.

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_j

R^-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 R^k
_ij are computed from the previous ones by

R^k
_ij = R^k-1
_ik (R^k-1
_kk)^* R^k-1
_kj | R^k-1
_ij

Example

Example DFA given to Kleene's algorithm

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₂,a)=q₁,
the start state q₀, and
set of accept states F = { q₁ }.

Kleene's algorithm computes the initial regular expressions as

R^-1 ₀₀ = a \| ε	R^-1 ₀₁ = b	R^-1 ₀₂ = ∅
R^-1 ₁₀ = ∅	R^-1 ₁₁ = b \| ε	R^-1 ₁₂ = a
R^-1 ₂₀ = ∅	R^-1 ₂₁ = a \| b	R^-1 ₂₂ = ε

Step 0:

R⁰ ₀₀ =	R⁰ ₀₁ =	R⁰ ₀₂ =
R⁰ ₁₀ =	R⁰ ₁₁ =	R⁰ ₁₂ =
R⁰ ₂₀ =	R⁰ ₂₁ =	R⁰ ₂₂ =

Step 1:

R¹ ₀₀ =	R¹ ₀₁ =	R¹ ₀₂ =
R¹ ₁₀ =	R¹ ₁₁ =	R¹ ₁₂ =
R¹ ₂₀ =	R¹ ₂₁ =	R¹ ₂₂ =

Step 2:

R² ₀₀ =	R² ₀₁ =	R² ₀₂ =
R² ₁₀ =	R² ₁₁ =	R² ₁₂ =
R² ₂₀ =	R² ₂₁ =	R² ₂₂ =

References

^ 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
^ Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automate" (PDF). Automata Studies, Annals of Math. Studies. 34. Princeton Univ. Press.
^ 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

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

[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

[1]

[2]

[3]