a) O que é o fecho de Kleene de um conjunto de seqüências?
b) Encontre o fecho de Kleene do conjunto \{11,0\}.

Passo 1

O enunciado pede duas coisas: (a) explicar o que é o fecho de Kleene de um conjunto de sequências (cadeias) e (b) calcular esse fecho para o conjunto S=\{11,0\}. O conteúdo envolve teoria de linguagens formais, mais especificamente o operador estrela (Kleene star) e concatenação de cadeias.

Passo 2

O fecho de Kleene de um conjunto S de cadeias, denotado por S^*, é definido como a união de todas as concatenações finitas de elementos de S. Formalmente,
S^* \;=\;\bigcup_{n=0}^{\infty} S^n,
onde
S^0 = \{\epsilon\} \quad\text{e}\quad S^n = \{\,x_1x_2\cdots x_n \mid x_i\in S\}\text{ para }n\ge1.
Aqui \epsilon é a cadeia vazia, e cada S^n contém todas as cadeias formadas por concatenar exatamente n elementos de S.

Passo 3

Vamos aplicar essa definição a S=\{11,0\}: S^0 contém apenas a cadeia vazia:
S^0 = \{\epsilon\}. S^1 é igual a S:
S^1 = \{11,\;0\}. S^2 contém todas as concatenações de duas cadeias de S:
S^2 = \{\,11\,11,\;11\,0,\;0\,11,\;0\,0\} = \{1111,\;110,\;011,\;00\}. S^3 teria oito cadeias, e assim por diante. Em geral
S^* = \{\,x_1x_2\cdots x_n \mid n\ge 0,\;x_i\in\{11,0\}\},
ou seja, todas as cadeias possíveis que se obtêm concatenando qualquer número de vezes “11” ou “0”, inclusive nenhuma (cadeia vazia).

Resposta

a) O fecho de Kleene de um conjunto S de cadeias é
S^* = \bigcup_{n=0}^{\infty} S^n,
onde S^0=\{\epsilon\} e S^n são as concatenações de n elementos de S.
b) Para S=\{11,0\},
S^* = \{\,x_1x_2\cdots x_n \mid n\ge 0,\;x_i\in\{11,0\}\} \;=\;\{\epsilon,\;11,\;0,\;1111,\;110,\;011,\;00,\;\dots\}.

Exercícios de Livros Relacionados