Fecho de Kleene

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 $\varepsilon$ (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_0=\{ \varepsilon \}\,$

definimos recursivamente o conjunto

$V_{i+1}=\{wv : w\in V_i \mbox{ and } v \in V\}\,$ em que $i \ge 0\,.$

Se $V$ é uma linguagem formal, então a $i$-ésima potência do conjunto $V$ é a abreviação da concatenação do conjunto $V$ com si mesmo $i$ vezes. Dessa forma, $V_i$ pode ser entendido como o conjunto de todas as cadeias de caracteres de tamanho $i$, formada pelos símbolos em $V$.

A definição do fecho de Kleene em $V$ é

$V^*=\bigcup_{i \in \N} V_i = \left \{ \epsilon \right\} \cup V_1 \cup V_2 \cup V_3 \cup \ldots$

Isto é, é a coleção de todas as cadeias de caracteres finitas geradas a partir dos símbolos em $V$.

Em alguns estudos de linguagens formais, uma variação do fecho de Kleene é a soma de Kleene, que omite $V_0$. Em outras palavras, a soma de Kleene em $V$ é

$V^+=\bigcup_{i \in \N^{\star}} V_i = V_1 \cup V_2 \cup V_3 \cup \ldots$

Exemplos

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

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