Álgebra de Kleene

Em matemática, uma álgebra de Kleene pode se referir a dois conceitos. Pode ser um reticulado distribuído limitado com uma involução que satisfaz os teoremas de De Morgan e . Logo, toda a álgebra booleana é uma álgebra de Kleene, mas a maioria das álgebras de Kleene não são álgebras booleanas. Assim como álgebras booleanas estão relacionadas à lógica proposicional clássica, as álgebras de Kleene estão relacionadas à lógica ternária. Também pode ser uma estrutura algébrica que generaliza as operações conhecidas através das expressões regulares.

Seu nome é uma referência ao matemático estado-unidense Stephen Cole Kleene, que, entretanto, não foi o responsável por sua definição. Ele introduziu as expressões regulares e questionou um conjunto completo de axiomas que permitiriam a derivação de todas as equações entre expressões regulares. O problema foi estudado originalmente por John Horton Conway com o nome de álgebras regulares. os axiomas das álgebras de Kleene resolvem o problema, como demonstrado por Dexter Kozen.

Definição

editar

Várias definições não equivalentes de álgebras de Kleene estão presentes na literatura.

Ponto de vista das expressões regulares

editar

Uma álgebra de Kleene é um conjunto A com duas operações binárias + ( ) e · ( ) e um operador unário * (fecho de Kleene;  ), de forma que os seguintes axiomas sejam satisfeitos:

  • Associatividade de + e ·:  
  • Comutatividade de +:  
  • Distributividade:  
  • Elementos neutros de + e ·:  
  •  

Os axiomas acima definem um semianel. Há ainda outros requisitos:

  • Idempotência de + :  

De acordo com os axiomas acima, pode-se concluir que uma álgebra de Kleene é um semianel idempotente. Agora é possível definir uma ordem parcial ≤ em A definindo ab se e somente se a + b = b (ou equivalentemente: ab se e somente se existe um x em A de forma que a + x = b). Com tal ordem pode-se formular os últimos axiomas da operação *:

  •  
  •  
  •  
  •  

Ponto de vista dos reticulados

editar

Seja um reticulado L que satisfaz os teoremas de De Morgan com um operador unário ~ em que  . Interpretando-se ' como ~, qualquer álgebra booleana também é uma álgebra de Kleene, mas a recíproca não é verdadeira.

Exemplos

editar

Seja Σ um conjunto finito (um alfabeto) e A o conjunto de todas as expressões regulares em Σ. Considera-se que duas dessas expressões regulares são iguais se elas descrevem a mesma linguagem. então A forma uma álgebra de Kleene.

Seja Σ um alfabeto e A o conjunto de todas as linguagens regulares em Σ (ou o conjunto de todas as linguagens livres de contexto em Σ; ou o conjunto de todas as linguagens recursivas em Σ; ou o conjunto de todas as linguagens em Σ). Então a união (+) e a concatenação (·) de dois elementos de A também pertence a A, assim como o fecho de Kleene aplicado a qualquer elemento de A. Obtém-se uma álgebra de Kleene A com 0 sendo o conjunto vazio e 1 sendo o conjunto que somente contém o conjunto vazio.

Seja M um monóide com elemento neutro e e seja A um conjunto de todos os subconjuntos de M. Para dois desses subconjuntos S e T, seja S + T a união de S e T e o conjunto ST = {st : s em S e t em T}. S* é definido como o submonóide de M gerado por S, que pode ser descrito como {e} ∪ SSSSSS ∪ ... Logo, A forma uma álgebra de Kleene com 0 sendo o conjunto vazio e 1 sendo {e}.

Toda álgebra booleana com operações   e   torna-se uma álgebra de Kleene se for usado   como +,   como · e a* = 1 para todo a.

Ver também

editar