Fecho de Kleene
Este artigo não cita fontes confiáveis. (Junho de 2012) |
Na lógica matemática e na ciência da computação, o fecho de Kleene, estrela de Kleene ou operador de Kleene, é uma operação unária aplicada a conjuntos. A aplicação do fecho de Kleene num conjunto V é escrito como V* (lê-se fecho de Kleene de V ou simplesmente V-estrela). É uma operação muito usada em expressões regulares, no contexto em que foi introduzida por Stephen Kleene para caracterizar certos tipos de autômatos.
- Se V é uma linguagem, então V* é o menor superconjunto de V que contém ε (denominado cadeia vazia) e é fechado numa operação de concatenação. Esse conjunto também pode ser descrito como o conjunto de todos elementos que podem ser formados através da concatenação de zero ou mais elementos de V.
- Se V é um alfabeto, então V* é o conjunto de todas as cadeias finitas de símbolos de V, incluindo a cadeia vazia.
Definição e notação
editarDado V0 = { ε } definimos recursivamente o conjunto Vi+1 = { wv : w ∈ Vi e v ∈ V } onde i ≥ 0. Se V é uma linguagem formal, então Vi representa a concatenação do conjunto V com si mesmo i vezes. Em outras palavras, Vi representa o conjunto de todas as cadeias de tamanho i, formada pelos elementos em V.
Assim, a definição do fecho de Kleene sobre a linguagem formal V é
Isto é, é a coleção de todas as cadeias finitas geradas a partir dos elementos em V.
Na literatura, especialmente no que tange expressões regulares, é possível encontrar uma variação do fecho de Kleene que omite V0, denominada soma de Kleene[carece de fontes]. A soma de Kleene sobre a linguagem formal V é
Exemplos
editarExemplos do fecho de Kleene aplicado a uma linguagem:
Exemplo do fecho de Kleene aplicado a um alfabeto:
