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 diz que
é um subconjunto de
, o conjunto de todas as cadeias (strings) sobre o alfabeto
, e pede para verificar se vale sempre a inclusão
Aqui o conteúdo é operações com linguagens formais: a potência
significa a concatenação de
consigo mesma.
Passo 2
Por definição,
Logo todo elemento de
é a concatenação de duas cadeias que já estão em
.
Passo 3
Para ver que nem sempre
, basta achar um contraexemplo. Tome
e
Então
Note que
mas
. Portanto não ocorre
.
Resposta
A inclusão
não é válida em geral. O contraexemplo é, por exemplo,
, pois aí
e
.