Suponha que
seja um subconjunto de
, em que
é um alfabeto. Demonstre ou mostre que não é válida cada uma destas afirmações.
se
, então
se
Passo 1
O enunciado trabalha com linguagens sobre um alfabeto
. Para uma linguagem
, define-se
A afirmação a ser testada é: “se
, então
”.
Passo 2
Para mostrar que a implicação não vale em geral, basta achar um contra-exemplo onde
mas
.
Passo 3
Tome
. Então
logo
. Contudo
. Isso refuta a afirmação original.
Resposta
A afirmação não é válida: um contra-exemplo é
, pois aí
mas
.