Fecho de Kleene

Predefinição:Sem-fontes 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.

1. 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.
2. 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

Dado V₀ = { ε } definimos recursivamente o conjunto V_i+1 = { wv : w ∈ V_i e v ∈ V } onde i ≥ 0. Se V é uma linguagem formal, então V_i representa a concatenação do conjunto V com si mesmo i vezes. Em outras palavras, V_i 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 é

$V^{*}=\bigcup _{i\in \mathbb{N}\cup \{0\}}{V}_i=\left\{\epsilon \right\}\cup V_1\cup V_2\cup V_3\cup \dots$

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 V₀, denominada soma de KleenePredefinição:Carece de fontes. A soma de Kleene sobre a linguagem formal V é

$V^{+}=V^{*}-\left\{\epsilon \right\}=\bigcup _{i\in \mathbb{N}-\{0\}}{V}_i=V_1\cup V_2\cup V_3\cup \dots$

Exemplos

Exemplos do fecho de Kleene aplicado a uma linguagem:

${\left\{𝖺𝖻,𝖼\right\}}^{\star }=\left\{\mathsf{\epsilon },𝖺𝖻,𝖼,𝖺𝖻𝖺𝖻,𝖺𝖻𝖼,𝖼𝖺𝖻,𝖼𝖼,𝖺𝖻𝖺𝖻𝖺𝖻,𝖺𝖻𝖺𝖻𝖼,𝖺𝖻𝖼𝖺𝖻,𝖺𝖻𝖼𝖼,𝖼𝖺𝖻𝖺𝖻,𝖼𝖺𝖻𝖼,𝖼𝖼𝖺𝖻,𝖼𝖼𝖼,\mathsf{\cdots }\right\}$

Exemplo do fecho de Kleene aplicado a um alfabeto:

${\left\{𝖺,𝖻,𝖼\right\}}^{\star }=\left\{\mathsf{\epsilon },𝖺,𝖻,𝖼,𝖺𝖺,𝖺𝖻,𝖺𝖼,𝖻𝖺,𝖻𝖻,𝖻𝖼,𝖼𝖺,𝖼𝖻,𝖼𝖼,\mathsf{\cdots }\right\}$

Ver também

• Álgebra de Kleene
• Formalismo de Backus-Naur Estendido
• Lema do bombeamento
• Expressões regulares