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^-1 ₀₀ (R^-1 ₀₀)^* R^-1 ₀₀ \| R^-1 ₀₀	= (a \| ε)	(a \| ε)^*	(a \| ε)	\| a \| ε	= a^*
R⁰ ₀₁	= R^-1 ₀₀ (R^-1 ₀₀)^* R^-1 ₀₁ \| R^-1 ₀₁	= (a \| ε)	(a \| ε)^*	b	\| b	= a^* b
R⁰ ₀₂	= R^-1 ₀₀ (R^-1 ₀₀)^* R^-1 ₀₂ \| R^-1 ₀₂	= (a \| ε)	(a \| ε)^*	∅	\| ∅	= ∅
R⁰ ₁₀	= R^-1 ₁₀ (R^-1 ₀₀)^* R^-1 ₀₀ \| R^-1 ₁₀	= ∅	(a \| ε)^*	(a \| ε)	\| ∅	= ∅
R⁰ ₁₁	= R^-1 ₁₀ (R^-1 ₀₀)^* R^-1 ₀₁ \| R^-1 ₁₁	= ∅	(a \| ε)^*	b	\| b \| ε	= b \| ε
R⁰ ₁₂	= R^-1 ₁₀ (R^-1 ₀₀)^* R^-1 ₀₂ \| R^-1 ₁₂	= ∅	(a \| ε)^*	∅	\| a	= a
R⁰ ₂₀	= R^-1 ₂₀ (R^-1 ₀₀)^* R^-1 ₀₀ \| R^-1 ₂₀	= ∅	(a \| ε)^*	(a \| ε)	\| ∅	= ∅
R⁰ ₂₁	= R^-1 ₂₀ (R^-1 ₀₀)^* R^-1 ₀₁ \| R^-1 ₂₁	= ∅	(a \| ε)^*	b	\| a \| b	= a \| b
R⁰ ₂₂	= R^-1 ₂₀ (R^-1 ₀₀)^* R^-1 ₀₂ \| R^-1 ₂₂	= ∅	(a \| ε)^*	∅	\| ε	= ε

Step 1:

R¹ ₀₀	= R⁰ ₀₀ (R⁰ ₀₀)^* R⁰ ₀₀ \| R⁰ ₀₀	=	^*	\| a^*	=
R¹ ₀₁	= R⁰ ₀₀ (R⁰ ₀₀)^* R⁰ ₀₁ \| R⁰ ₀₁	=	^*	\| a^* b	=
R¹ ₀₂	= R⁰ ₀₀ (R⁰ ₀₀)^* R⁰ ₀₂ \| R⁰ ₀₂	=	^*	\| ∅	=
R¹ ₁₀	= R⁰ ₁₀ (R⁰ ₀₀)^* R⁰ ₀₀ \| R⁰ ₁₀	=	^*	\| ∅	=
R¹ ₁₁	= R⁰ ₁₀ (R⁰ ₀₀)^* R⁰ ₀₁ \| R⁰ ₁₁	=	^*	\| b \| ε	=
R¹ ₁₂	= R⁰ ₁₀ (R⁰ ₀₀)^* R⁰ ₀₂ \| R⁰ ₁₂	=	^*	\| a	=
R¹ ₂₀	= R⁰ ₂₀ (R⁰ ₀₀)^* R⁰ ₀₀ \| R⁰ ₂₀	=	^*	\| ∅	=
R¹ ₂₁	= R⁰ ₂₀ (R⁰ ₀₀)^* R⁰ ₀₁ \| R⁰ ₂₁	=	^*	\| a \| b	=
R¹ ₂₂	= R⁰ ₂₀ (R⁰ ₀₀)^* R⁰ ₀₂ \| R⁰ ₂₂	=	^*	\| ε	=

Step 2:

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]