Fecho de Kleene

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes (desde junho de 2012). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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[editar | editar código-fonte]

Dado 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 é

 V^*=\bigcup_{i \in \N \cup \{0\} } V_i = \left \{ \varepsilon \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 V0, denominada soma de Kleene[carece de fontes?]. A soma de Kleene sobre a linguagem formal V é

V^+ = V^* - \left\{ \varepsilon \right\} =\bigcup_{i \in \N - \{0\}} V_i = V_1 \cup V_2 \cup V_3 \cup \dots

Exemplos[editar | editar código-fonte]

Exemplos do fecho de Kleene aplicado a uma linguagem:

\left \{ \mathsf{{\color{Blue}ab},{\color{Red}c}} \right\}^\star = \left \{ \mathsf{\varepsilon,{\color{Blue}ab},{\color{Red}c},{\color{Blue}abab},{\color{Blue}ab}{\color{Red}c},{\color{Red}c}{\color{Blue}ab},{\color{Red}cc},{\color{Blue}ababab},{\color{Blue}abab}{\color{Red}c},{\color{Blue}ab{\color{Red}c}ab},{\color{Blue}ab}{\color{Red}cc},{\color{Red}c}{\color{Blue}abab},{\color{Red}c{\color{Blue}ab}c},{\color{Red}cc}{\color{Blue}ab},{\color{Red}ccc},\cdots} \right\}

Exemplo do fecho de Kleene aplicado a um alfabeto:

\left\{ \mathsf{ {\color{Blue}a},{\color{YellowOrange}b},{\color{Red}c} }\right\}^\star = \left\{ \mathsf{\varepsilon,{\color{Blue}a},{\color{YellowOrange}b},{\color{Red}c},{\color{Blue}aa},{\color{Blue}a}{\color{YellowOrange}b},{\color{Blue}a}{\color{Red}c},{\color{YellowOrange}b}{\color{Blue}a},{\color{YellowOrange}bb},{\color{YellowOrange}b}{\color{Red}c},{\color{Red}c}{\color{Blue}a},{\color{Red}c}{\color{YellowOrange}b},{\color{Red}cc},\cdots} \right\}

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