Que conjunto de seqüências com símbolos no conjunto \{0,1, 2\} é representado pela expressão regular \left(2^{*}\right)\left(0 \cup\left(12^{*}\right)\right)^{*} ?

Passo 1

O enunciado pede para descrever, em linguagem natural, o conjunto de sequências sobre o alfabeto \{0,1,2\} gerado pela expressão regular
(2^*)\,(0 \;\cup\;(1\,2^*))^*
Aqui o conteúdo é teoria de linguagens formais e expressões regulares. Vamos interpretar cada parte e, ao final, dar uma descrição equivalente mais simples.

Passo 2

Interpretação de 2^*: 2^* é o conjunto de todas as cadeias formadas apenas pelo símbolo 2, inclusive a cadeia vazia. Ou seja, qualquer número (zero ou mais) de “2” no começo da sequência.

Passo 3

Interpretação de (0 \cup (1\,2^*))^*:
0 \;\cup\;(1\,2^*)
é o conjunto que contém
– a cadeia “ \,0\”, ou
– as cadeias que começam com “ \,1” seguidas de qualquer número de “ \,2”.
E o operador estrela externo “ \,^*” indica que podemos concatenar um número arbitrário (até zero) desses blocos, um após o outro.

Passo 4

Juntando as duas partes, a expressão completa
2^*\,(0 \cup (1\,2^*))^*
gera exatamente as cadeias que:
  1. têm um bloco inicial de “ \,2”s (talvez nenhum),
  2. seguido de zero ou mais blocos, em que cada bloco é ou “ \,0” ou “ \,1” seguido de um monte de “ \,2”s.

Passo 5

Caracterização mais simples:
– Como todo “ \,2” que aparece após o bloco inicial só pode vir imediatamente depois de um “ \,1”, nunca aparece um “ \,2” logo após um “ \,0”.
– Portanto essas são precisamente as cadeias em \{0,1,2\}^* que não contêm o subcadeia “ \,02**” em nenhuma posição (embora possam começar com “ \,2”s).

Resposta

O conjunto gerado é
\{\,w\in\{0,1,2\}^* \mid \text{não existe a substring “02” em }w\}.ã

Exercícios de Livros Relacionados