a) O que é o fecho de Kleene de um conjunto de seqüências?
b) Encontre o fecho de Kleene do conjunto
.
b) Encontre o fecho de Kleene do conjunto
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
. 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
de cadeias, denotado por
, é definido como a união de todas as concatenações finitas de elementos de
. Formalmente,
onde
Aqui
é a cadeia vazia, e cada
contém todas as cadeias formadas por concatenar exatamente
elementos de
.
Passo 3
Vamos aplicar essa definição a
:
contém apenas a cadeia vazia:
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
de cadeias é
onde
e
são as concatenações de
elementos de
.
b) Para ,
b) Para