Fecho de Kleene


O fecho de Kleene descreve o conjunto de todas as palavras possíveis geradas por zero ou mais concatenações dos elementos de uma linguagem .

Ele é denotado por e representa a união de todas as potências finitas de .

Formalmente, se é uma linguagem sobre um alfabeto , o fecho de Kleene é definido como:

Isso significa que , onde cada é a linguagem resultante da concatenação de consigo mesma vezes.

Note

A palavra vazia está sempre em , independentemente de conter ou não , devido uma das propriedades do Fecho de Kleene.

Exemplo Prático

Considere o alfabeto e a linguagem :

  • ,
  • ,
  • ,
  • ,
  • e assim por diante.

Portanto:

Nesse caso, representa todas as palavras possíveis sobre o alfabeto , incluindo a palavra vazia e cadeias de qualquer comprimento formadas apenas por “a”.

Outro exemplo: Se :

  • ,
  • ,
  • ,
  • , e assim por diante.

Então, contém , todas as palavras de , todas as combinações de duas palavras de , e assim sucessivamente, formando um conjunto infinito.

Sua Importância em Autômatos

O fecho de Kleene é essencial na teoria de autômatos porque está diretamente relacionado às linguagens regulares. Uma linguagem é regular se pode ser expressa por uma expressão regular, e o operador estrela (*) nas expressões regulares corresponde exatamente ao fecho de Kleene.

Por exemplo, a expressão gera a linguagem , que é reconhecida por um autômato finito.

Referências


Aula 2 - Alfabetos palavras e linguagens