Á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
editarVárias definições não equivalentes de álgebras de Kleene estão presentes na literatura.
Ponto de vista das expressões regulares
editarUma á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 a ≤ b se e somente se a + b = b (ou equivalentemente: a ≤ b 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
editarSeja 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
editarSeja Σ 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} ∪ S ∪ SS ∪ SSS ∪ ... 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.