Demonstre ou mostre que é falsa cada uma destas afirmações para os subconjuntos
e
de
, em que
é um alfabeto.
a)
a)
Passo 1
O enunciado pede para mostrar que, para quaisquer linguagens
,
e
sobre o alfabeto
, vale a igualdade
O conteúdo envolvido é a definição de concatenação de linguagens e a propriedade distributiva da concatenação sobre a união.
Passo 2
Mostramos primeiro que
Seja
. Pela definição de concatenação, existem
e
tais que
. Como
, ou
ou
.
- Se
, então . - Se
, então .
Em ambos os casos,. Logo
Passo 3
Agora mostramos que
Seja
. Então
ou
.
- Se
, existem e com . Como , segue . - Se
, existem e com . Como , segue .
Assim
Passo 4
Pelas inclusões dos Passos 2 e 3, concluímos que
Resposta
A igualdade
é verdadeira.