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, Σ, δ, q0, F), com Q = { q0,...,qn } sendo seu conjunto de estados, o algoritmo computa o R do conjunto de todas as palavras que levam M do estado qi ao qj 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 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 0j epresenta o conjunto de todas as palavras que levam M do seu estado inicial q0 a qj. Se F = { q1,...,qf } é o conjunto de estados de aceitação, a expressão regular Rn 01 | ... | Rn 0f representa a linguagem aceita por M.

As expressões regulares iniciais, para k = -1, são computadas como R = a1 | ... | am       if i≠j, onde δ(qi,a1) = ... = δ(qi,am) = qj R = a1 | ... | am | ε, if i=j, onde δ(qi,a1) = ... = δ(qi,am) = qj

Após isso, em cada passo as expressões Rk ij são computadas a partir das anteriores por R = R (R)* R | R

Exemplo thumb|Exemplo de AFD dado como entrada ao Algoritmo de Kleene O autômato mostrado na figura pode ser descrito como M = (Q, Σ, δ, q0, F), como sendo o conjunto de estados Q = { q0, q1, q2 }, o alfabeto de entrada Σ = { a, b }, a função de transição δ com δ(q0,a)=q0,   δ(q0,b)=q1,   δ(q1,a)=q2,   δ(q1,b)=q1,   δ(q2,a)=q1, e δ(q2,b)=q1, o estado inicial q0, e conjunto de estados de aceitação F = { q1 }. O algoritmo de Kleene computa a expressão regular inicial como R     = a | ε R = b R = ∅ R = ∅ R = b | ε R = a R = ∅ R = a | b R = ε

Após isso, os R são computados através de R 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:

R     = R (R)* R | R     = (a | ε) (a | ε)* (a | ε) | a | ε     = a* R = R (R)* R | R = (a | ε) (a | ε)* b | b = a* b R = R (R)* R | R = (a | ε) (a | ε)* ∅ | ∅ = ∅ R = R (R)* R | R = ∅ (a | ε)* (a | ε) | ∅ = ∅ R = R (R)* R | R = ∅ (a | ε)* b | b | ε = b | ε R = R (R)* R | R = ∅ (a | ε)* ∅ | a = a R = R (R)* R | R = ∅ (a | ε)* (a | ε) | ∅ = ∅ R = R (R)* R | R = ∅ (a | ε)* b | a | b = a | b R = R (R)* R | R = ∅ (a | ε)* ∅ | ε = ε

Passo 1:

R     = R (R)* R | R     = a*b (b | ε)* ∅ | a*         = a* R = R (R)* R | R = a*b (b | ε)* (b | ε) | a* b = a* b* b R = R (R)* R | R = a*b (b | ε)* a | ∅ = a* b* ba R = R (R)* R | R = (b | ε) (b | ε)* ∅ | ∅ = ∅ R = R (R)* R | R = (b | ε) (b | ε)* (b | ε) | b | ε = b* R = R (R)* R | R = (b | ε) (b | ε)* a | a = b* a R = R (R)* R | R = (a | b) (b | ε)* ∅ | ∅ = ∅ R = R (R)* R | R = (a | b) (b | ε)* (b | ε) | a | b = (a | b) b* R = R (R)* R | R = (a | b) (b | ε)* a | ε = (a | b) b* a | ε

Passo 2: R     = R (R)* R | R     = a*b*ba ((a|b)b*a | ε)* ∅ | a* = a* R = R (R)* R | R = a*b*ba ((a|b)b*a | ε)* (a|b)b* | a* b* b = R = R (R)* R | R = a*b*ba ((a|b)b*a | ε)* ((a|b)b*a | ε) | a* b* ba = R = R (R)* R | R = b* a ((a|b)b*a | ε)* ∅ | ∅ = ∅ R = R (R)* R | R = b* a ((a|b)b*a | ε)* (a|b)b* | b* = R = R (R)* R | R = b* a ((a|b)b*a | ε)* ((a|b)b*a | ε) | b* a = R = R (R)* R | R = ((a|b)b*a | ε) ((a|b)b*a | ε)* ∅ | ∅ = ∅ R = R (R)* R | R = ((a|b)b*a | ε) ((a|b)b*a | ε)* (a|b)b* | (a | b) b* = R = R (R)* R | R = ((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 q0 é o estado inicial, e q1 é o único estado de aceitação, a expressão regular R denota o conjunto de todas as palavras aceitas pelo autômato.

Ver 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

Categoria:Algoritmos