Determine se a seqüência 11101 está em cada um destes conjuntos.
Passo 1
O enunciado pede para verificar se a sequência
pertence ao conjunto definido pela expressão
. Aqui vamos usar a noção de estrela de Kleene (repetição de blocos) e concatenação de linguagens.
Passo 2
A linguagem
é o conjunto de todas as cadeias formadas pela concatenação de zero ou mais cópias de “111”, ou seja
Passo 3
A linguagem
é o conjunto de todas as cadeias de zeros (incluindo a vazia) e
contém apenas a cadeia “1”.
Passo 4
Uma cadeia
pertence a
se existir decomposição
com
,
e
. Para
podemos escolher
De fato,
é uma cópia de “111”,
é uma cópia de “0” e
é “1”. Logo essa decomposição mostra que
Resposta
Sim, a sequência
pertence ao conjunto
.