Determine se a seqüência 11101 está em cada um destes conjuntos.
{111}\^{*}\{0}\^{*}\{1}

Passo 1

O enunciado pede para verificar se a sequência 11101 pertence ao conjunto definido pela expressão \{111\}^*\{0\}^*\{1\}. Aqui vamos usar a noção de estrela de Kleene (repetição de blocos) e concatenação de linguagens.

Passo 2

A linguagem \{111\}^* é o conjunto de todas as cadeias formadas pela concatenação de zero ou mais cópias de “111”, ou seja
\{111\}^* = \{\varepsilon,\,111,\,111111,\,111111111,\dots\}.

Passo 3

A linguagem \{0\}^* é o conjunto de todas as cadeias de zeros (incluindo a vazia) e \{1\}=\{\text{"1"}\} contém apenas a cadeia “1”.

Passo 4

Uma cadeia x pertence a \{111\}^*\{0\}^*\{1\} se existir decomposição
x = u\,v\,w
com u\in\{111\}^*, v\in\{0\}^* e w\in\{1\}. Para x=11101 podemos escolher
u = 111,\quad v = 0,\quad w = 1.
De fato, u é uma cópia de “111”, v é uma cópia de “0” e w é “1”. Logo essa decomposição mostra que
11101 \;\in\;\{111\}^*\{0\}^*\{1\}.

Resposta

Sim, a sequência 11101 pertence ao conjunto \{111\}^*\{0\}^*\{1\}.

Exercícios de Livros Relacionados