Álgebra de Kleene

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 ( x \wedge \sim x ) \le ( y \vee \sim y ). 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 | editar código-fonte]

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

Ponto de vista das expressões regulares[editar | editar código-fonte]

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

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

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 *:

  • \forall a \in A \quad 1+aa^* \le a^*
  • \forall a \in A \quad 1+a^*a \le a^*
  • \forall a,x \in A, ax \le x \to a^*x \le x
  • \forall a,x \in A, xa \le x \to xa^* \le x

Ponto de vista dos reticulados[editar | editar código-fonte]

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

Exemplos[editar | editar código-fonte]

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 \lor e \land torna-se uma álgebra de Kleene se for usado \lor como +, \land como · e a* = 1 para todo a.

Ver também[editar | editar código-fonte]