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 pede para verificar a identidade
onde
. Nosso objetivo é mostrar que essa igualdade em geral não é válida, fornecendo o contra-exemplo apropriado.
Passo 2
Recordemos as definições:
onde
e
.
Por sua vez,
Por sua vez,
Logo
.
Passo 3
Vimos que
. Mas por definição
não contém a cadeia vazia
, ao contrário de
, que sempre contém
.
Passo 4
Contra-exemplo concreto: seja
.
Então
Então
Como
mas
, temos
Resposta
A igualdade
não é válida em geral; de fato
.