Algoritmo de Kleene

No ramo da Ciência da computação teórica, em particular na teoria das Linguagens formais, o Algoritmo de Kleene faz a transformação de um dado Autômato finito determinístico (AFD) em uma Expressão regular. Junto com outros algoritmos de conversão, ele estabelece a equivalência de vários formatos de descrições de linguagens regulares.

Descrição do Algoritmo

De acordo com Gross and Yellen (2004), este algoritmo pode ser rastreado até o matemático Stephen Kleene (1956).

A descrição aqui apresentada segue segundo Hopcroft and Ullman (1979). Onde dado um Autômato finito determinístico M = (Q, Σ, δ, q₀, F), com Q = { q₀,...,q_n } sendo seu conjunto de estados, o algoritmo computa

o Rk
ij do conjunto de todas as palavras que levam M do estado q_i ao q_j sem passar por qualquer estado com numeração maior que k.

Aqui, “passar por um estado” significa entrar e sair dele, então ambos i e j podem ser maiores do que k, porém nenhum estado intermediário pode. Cada Rk ijk
ij do conjunto é representado por uma expressão regular; o algoritmo às computa passo a passo para k = -1, 0, ..., n. isto que não há nenhum estado com numeração maior do que n, a expressão regular Rn 0jn
0j epresenta o conjunto de todas as palavras que levam M do seu estado inicial q₀ a q_j. Se F = { q₁,...,q_f } é o conjunto de estados de aceitação, a expressão regular Rn 01n
01 | ... | Rn 0fn
0f representa a linguagem aceita por M.

As expressões regulares iniciais, para k = -1, são computadas como

R-1
ij = a₁ | ... | a_m       if i≠j, onde δ(q_i,a₁) = ... = δ(q_i,a_m) = q_j

R-1
ij = a₁ | ... | a_m | ε, if i=j, onde δ(q_i,a₁) = ... = δ(q_i,a_m) = q_j

Após isso, em cada passo as expressões Rk ijk
ij são computadas a partir das anteriores por

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

Exemplo

Exemplo de AFD dado como entrada ao Algoritmo de Kleene

O autômato mostrado na figura pode ser descrito como M = (Q, Σ, δ, q₀, F), como sendo

• o conjunto de estados Q = { q₀, q₁, q₂ },
• o alfabeto de entrada Σ = { a, b },
• a função de transição δ com δ(q₀,a)=q₀,   δ(q₀,b)=q₁,   δ(q₁,a)=q₂,   δ(q₁,b)=q₁,   δ(q₂,a)=q₁, e δ(q₂,b)=q₁,
• o estado inicial q₀, e
• conjunto de estados de aceitação F = { q₁ }.

O algoritmo de Kleene computa a expressão regular inicial como

R-1 00	= a | ε
R-1 01	= b
R-1 02	= ∅
R-1 10	= ∅
R-1 11	= b | ε
R-1 12	= a
R-1 20	= ∅
R-1 21	= a | b
R-1 22	= ε

Após isso, os Rk
ij são computados através de Rk-1
ij passo a passo para k = 0, 1, 2. Igualidades da Kleene algebra são usadas para simplificar a expressão regular o máximo possível.

Passo 0:

R0 00	= R-1 00 (R-1 00)* R-1 00 | R-1 00	= (a | ε)	(a | ε)*	(a | ε)	| a | ε	= a*
R0 01	= R-1 00 (R-1 00)* R-1 01 | R-1 01	= (a | ε)	(a | ε)*	b	| b	= a* b
R0 02	= R-1 00 (R-1 00)* R-1 02 | R-1 02	= (a | ε)	(a | ε)*	∅	| ∅	= ∅
R0 10	= R-1 10 (R-1 00)* R-1 00 | R-1 10	= ∅	(a | ε)*	(a | ε)	| ∅	= ∅
R0 11	= R-1 10 (R-1 00)* R-1 01 | R-1 11	= ∅	(a | ε)*	b	| b | ε	= b | ε
R0 12	= R-1 10 (R-1 00)* R-1 02 | R-1 12	= ∅	(a | ε)*	∅	| a	= a
R0 20	= R-1 20 (R-1 00)* R-1 00 | R-1 20	= ∅	(a | ε)*	(a | ε)	| ∅	= ∅
R0 21	= R-1 20 (R-1 00)* R-1 01 | R-1 21	= ∅	(a | ε)*	b	| a | b	= a | b
R0 22	= R-1 20 (R-1 00)* R-1 02 | R-1 22	= ∅	(a | ε)*	∅	| ε	= ε

Passo 1:

R1 00	= R0 01 (R0 11)* R0 10 | R0 00	= a*b	(b | ε)*	∅	| a*	= a*
R1 01	= R0 01 (R0 11)* R0 11 | R0 01	= a*b	(b | ε)*	(b | ε)	| a* b	= a* b* b
R1 02	= R0 01 (R0 11)* R0 12 | R0 02	= a*b	(b | ε)*	a	| ∅	= a* b* ba
R1 10	= R0 11 (R0 11)* R0 10 | R0 10	= (b | ε)	(b | ε)*	∅	| ∅	= ∅
R1 11	= R0 11 (R0 11)* R0 11 | R0 11	= (b | ε)	(b | ε)*	(b | ε)	| b | ε	= b*
R1 12	= R0 11 (R0 11)* R0 12 | R0 12	= (b | ε)	(b | ε)*	a	| a	= b* a
R1 20	= R0 21 (R0 11)* R0 10 | R0 20	= (a | b)	(b | ε)*	∅	| ∅	= ∅
R1 21	= R0 21 (R0 11)* R0 11 | R0 21	= (a | b)	(b | ε)*	(b | ε)	| a | b	= (a | b) b*
R1 22	= R0 21 (R0 11)* R0 12 | R0 22	= (a | b)	(b | ε)*	a	| ε	= (a | b) b* a | ε

Passo 2:

R2 00	= R1 02 (R1 22)* R1 20 | R1 00	= a*b*ba	((a|b)b*a | ε)*	∅	| a*	= a*
R2 01	= R1 02 (R1 22)* R1 21 | R1 01	= a*b*ba	((a|b)b*a | ε)*	(a|b)b*	| a* b* b	=
R2 02	= R1 02 (R1 22)* R1 22 | R1 02	= a*b*ba	((a|b)b*a | ε)*	((a|b)b*a | ε)	| a* b* ba	=
R2 10	= R1 12 (R1 22)* R1 20 | R1 10	= b* a	((a|b)b*a | ε)*	∅	| ∅	= ∅
R2 11	= R1 12 (R1 22)* R1 21 | R1 11	= b* a	((a|b)b*a | ε)*	(a|b)b*	| b*	=
R2 12	= R1 12 (R1 22)* R1 22 | R1 12	= b* a	((a|b)b*a | ε)*	((a|b)b*a | ε)	| b* a	=
R2 20	= R1 22 (R1 22)* R1 20 | R1 20	= ((a|b)b*a | ε)	((a|b)b*a | ε)*	∅	| ∅	= ∅
R2 21	= R1 22 (R1 22)* R1 21 | R1 21	= ((a|b)b*a | ε)	((a|b)b*a | ε)*	(a|b)b*	| (a | b) b*	=
R2 22	= R1 22 (R1 22)* R1 22 | R1 22	= ((a|b)b*a | ε)	((a|b)b*a | ε)*	((a|b)b*a | ε)	| (a | b) b* a | ε	=

((simplificação do passo 2 a ser completada))

Visto que q₀ é o estado inicial, e q₁ é o único estado de aceitação, a expressão regular R2
01 denota o conjunto de todas as palavras aceitas pelo autômato.

Veja também

• Algoritmo de Floyd-Warshall — um algoritmo sobre grafos ponderados que pode ser implementado pelo algoritmo e Kleene, usando uma Kleene algebra particular.
• Problema da altura da estrela — qual é a mínima profundidade aninhada da estrela de Kleene de todas as expressões regulares correspondentes a um dado AFD?
• Generalized star height problem — se um operador de complemento é permitido adicionalmente em expressões regulares, pode a profundidade do aninhamento da estrela da saída do algoritmo de Kleene ter um limite fixo?
• Algoritmo de Thompson — transforma uma expressão regular em um autômato finito.