Que conjunto de seqüências com símbolos no conjunto
,
é representado pela expressão regular
?
Passo 1
O enunciado pede para descrever, em linguagem natural, o conjunto de sequências sobre o alfabeto
gerado pela expressão regular
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
:
é o conjunto de todas as cadeias formadas apenas pelo símbolo
, 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
:
é o conjunto que contém
– a cadeia “ \”, ou
– as cadeias que começam com “ ” seguidas de qualquer número de “
”.
– a cadeia “
– as cadeias que começam com “
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
gera exatamente as cadeias que:
- têm um bloco inicial de “
”s (talvez nenhum), - seguido de zero ou mais blocos, em que cada bloco é ou “
” ou “ ” seguido de um monte de “ ”s.
Passo 5
Caracterização mais simples:
– Como todo “ ” que aparece após o bloco inicial só pode vir imediatamente depois de um “
”, nunca aparece um “
” logo após um “
”.
– Portanto essas são precisamente as cadeias em que não contêm o subcadeia “
**” em nenhuma posição (embora possam começar com “
”s).
– Como todo “
– Portanto essas são precisamente as cadeias em
Resposta
O conjunto gerado é