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

editar

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

A descrição aqui apresentada segue segundo Hopcroft and Ullman (1979).[3] 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 Rk
ij
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 ij 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 q0 a qj. Se F = { q1,...,qf } é 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
= a1 | ... | am       if ij, onde δ(qi,a1) = ... = δ(qi,am) = qj
R-1
ij
= a1 | ... | am | ε, if i=j, onde δ(qi,a1) = ... = δ(qi,am) = qj

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

editar
 
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-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 q0 é o estado inicial, e q1 é 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

editar
  • 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

editar
  1. 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 
  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 
  3. John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. [S.l.]: Addison-Wesley. ISBN 0-201-02988-X