Suponha que A seja um subconjunto de V^{*}, em que V é um alfabeto. Demonstre ou mostre que não é válida cada uma destas afirmações.
A \subseteq A^{2}

Passo 1

O enunciado diz que A é um subconjunto de V^{*}, o conjunto de todas as cadeias (strings) sobre o alfabeto V, e pede para verificar se vale sempre a inclusão
A \subseteq A^{2}.
Aqui o conteúdo é operações com linguagens formais: a potência A^{2} significa a concatenação de A consigo mesma.

Passo 2

Por definição,
A^{2} = \{\,xy \mid x\in A \text{ e } y\in A\}.
Logo todo elemento de A^{2} é a concatenação de duas cadeias que já estão em A.

Passo 3

Para ver que nem sempre A\subseteq A^{2}, basta achar um contraexemplo. Tome V=\{a\} e
A = \{a\}.
Então
A^{2} = \{\,xy \mid x\in\{a\},\,y\in\{a\}\} = \{aa\}.
Note que a\in A mas a\notin A^{2}. Portanto não ocorre A\subseteq A^{2}.

Resposta

A inclusão A\subseteq A^{2} não é válida em geral. O contraexemplo é, por exemplo, A=\{a\}, pois aí A^{2}=\{aa\} e a\notin A^{2}.

Exercícios de Livros Relacionados