Supor que
e
são duas expressões regulares diferentes. Então, as linguagens representadas por
e
:
(a) Podem ser iguais.
(b) São diferentes.
(c) São iguais.
(d) Impossível tirar qualquer conclusão.
(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
e
são duas expressões regulares diferentes e pergunta o que podemos concluir sobre as linguagens
e
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
e .
Embora e
sejam diferentes como escrita, ambas descrevem a mesma linguagem
e
Embora
Passo 4
Como acabamos de ver, expressões regulares diferentes podem representar a mesma linguagem. Portanto não podemos afirmar que
e
sejam sempre diferentes nem sempre iguais — elas simplesmente podem coincidir.
Resposta
(a) Podem ser iguais.