# 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$_0$, F), com Q = { q$_0$,...,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$_0$ a q$_j$. Se F = { q$_1$,...,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$_1$ | ... | a$_m$   if i≠j, onde δ(q$_i$,a$_1$) = ... = δ(q$_i$,a$_m$) = q$_j$
    R-1 ij = a$_1$ | ... | a$_m$ | ε, if i=j, onde δ(q$_i$,a$_1$) = ... = δ(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

O autômato mostrado na figura pode ser descrito como M = (Q, Σ, δ, q$_0$, F), como sendo
* o conjunto de estados Q = { q$_0$, q$_1$, q$_2$ },
* o alfabeto de entrada Σ = { a, b },
* a função de transição δ com δ(q$_0$,a)=q$_0$, δ(q$_0$,b)=q$_1$, δ(q$_1$,a)=q$_2$, δ(q$_1$,b)=q$_1$, δ(q$_2$,a)=q$_1$, e δ(q$_2$,b)=q$_1$,
* o estado inicial q$_0$, e
* conjunto de estados de aceitação F = { q$_1$ }.
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$_0$ é o estado inicial, e q$_1$ é 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.

## Referencias

* ↑ Jonathan L. Gross and Jay Yellen, ed. (2004). Handbook of Graph Theory. Col: Discrete Mathematics and it Applications. [S.l.]: CRC Press. ISBN 1-58488-090-2
* ↑ Kleene, Stephen C. (1956). «Representation of Events in Nerve Nets and Finite Automate» (PDF). Princeton Univ. Press. Automata Studies, Annals of Math. Studies. 34
* ↑ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. [S.l.]: Addison-Wesley. ISBN 0-201-02988-X