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

Passo 1

O enunciado pede para verificar se a sequência de caracteres \mathtt{11101} pertence ao conjunto definido pelo “regular expression”
\{1\}^*\,\{0\}^*\,\{1\}^*
Este conteúdo faz parte de linguagens formais e expressões regulares. Para resolver, basta entender que \{1\}^*\,\{0\}^*\,\{1\}^* é o conjunto de todas as cadeias da forma
1^i\,0^j\,1^k
com i,j,k\ge0.

Passo 2

Explicando o padrão 1^i\,0^j\,1^k:
  • 1^i representa uma sequência de i símbolos “1” (podendo ser i=0, i.e.\ vazio);
  • 0^j representa uma sequência de j símbolos “0” (podendo ser j=0);
  • 1^k representa uma sequência de k símbolos “1” (podendo ser k=0).
    Ou seja, qualquer número de “1”, seguido de qualquer número de “0”, seguido de qualquer número de “1”.

Passo 3

Agora, tomamos a sequência \mathtt{11101} e a separamos em três blocos conforme o padrão:
  • Prefixo de “1”: \mathtt{111} → aqui i=3.
  • Bloco de “0”: \mathtt{0} → aqui j=1.
  • Sufixo de “1”: \mathtt{1} → aqui k=1.
    Como conseguimos escrever \mathtt{11101} = 1^3\,0^1\,1^1, ela satisfaz o padrão 1^i\,0^j\,1^k.

Resposta

Sim. A sequência \mathtt{11101} pertence ao conjunto \{1\}^*\{0\}^*\{1\}^*.

Exercícios de Livros Relacionados