Demonstre ou mostre que é falsa cada uma destas afirmações para os subconjuntos
e
de
, em que
é um alfabeto.
b)
b)
Passo 1
Resumo do enunciado e conceito
Temos três linguagens . Queremos ver se vale
Temos três linguagens
Aqui a concatenação de linguagens é dada por
e a interseção é a usual de conjuntos.
Passo 2
Inclusão
Se , então existem
e
tais que
. Como
e
, segue que
e também
. Logo
Se
e, portanto,
Passo 3
Contraexemplo para a inclusão inversa
Vamos ver que nem sempre .
Escolhemos
Vamos ver que nem sempre
Escolhemos
Então
Por outro lado,
de modo que
O elemento
pertence a
mas não a
, pois este último é vazio.
Resposta
A igualdade
é em geral falsa. O contraexemplo acima mostra que a inclusão inversa não vale.