Supor que r e s são duas expressões regulares diferentes. Então, as linguagens representadas por r e s :
(a) Podem ser iguais.
(b) São diferentes.
(c) São iguais.
(d) Impossível tirar qualquer conclusão.

Passo 1

O enunciado diz que r e s são duas expressões regulares diferentes e pergunta o que podemos concluir sobre as linguagens L(r) e L(s) que elas descrevem. O conteúdo envolve a definição de expressão regular e equivalência de linguagens regulares.

Passo 2

Por teoria de linguagens formais, uma expressão regular é apenas uma forma de descrever uma linguagem regular. Não há garantia de que duas expressões diferentes gerem linguagens distintas; duas notações distintas podem denotar exatamente o mesmo conjunto de cadeias.

Passo 3

Um exemplo clássico é tomar \texttt{r = a|b}
e \texttt{s = b|a}.
Embora r e s sejam diferentes como escrita, ambas descrevem a mesma linguagem
L = \{\,a,\,b\}.

Passo 4

Como acabamos de ver, expressões regulares diferentes podem representar a mesma linguagem. Portanto não podemos afirmar que L(r) e L(s) sejam sempre diferentes nem sempre iguais — elas simplesmente podem coincidir.

Resposta

(a) Podem ser iguais.

Exercícios relacionados