Suponha que
seja um subconjunto de
, em que
é um alfabeto. Demonstre ou mostre que não é válida cada uma destas afirmações.
Passo 1
O enunciado considera uma linguagem
e o símbolo
como a cadeia vazia em
. A afirmação a verificar é
Isso envolve a operação de concatenação entre linguagem e cadeia. Vamos mostrar que essa igualdade é sempre verdadeira.
Passo 2
Primeiro mostramos
. Seja
.
Por definição de concatenação de linguagens, existe e
tal que
Por definição de concatenação de linguagens, existe
Mas o único elemento de
é
, e concatenar qualquer cadeia
com
dá
. Logo
Como
, segue que
. Assim,
.
Passo 3
Agora mostramos
. Seja
. Note que
pois concatenar
à direita de
não altera
. Como
e
, a definição de concatenação garante que
. Logo
.
Resposta
Como temos
e
, concluímos que