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^{*} A=A^{*}

Passo 1

O enunciado pede para verificar a identidade
A^{*}A = A^{*}
onde A\subseteq V^{*}. Nosso objetivo é mostrar que essa igualdade em geral não é válida, fornecendo o contra-exemplo apropriado.

Passo 2

Recordemos as definições:
A^{*} = \bigcup_{n=0}^{\infty} A^{n},
onde A^{0}=\{\varepsilon\} e A^{n+1}=A^{n}A.
Por sua vez,
A^{*}A = \bigl(\bigcup_{n=0}^{\infty} A^{n}\bigr)A = \bigcup_{n=0}^{\infty} (A^{n}A) = \bigcup_{m=1}^{\infty} A^{m} = A^{+}.
Logo A^{*}A = A^{+}.

Passo 3

Vimos que A^{*}A=A^{+}. Mas por definição
A^{+} = \bigcup_{m=1}^{\infty} A^{m}
não contém a cadeia vazia \varepsilon, ao contrário de A^{*}, que sempre contém \varepsilon.

Passo 4

Contra-exemplo concreto: seja A=\{a\}.
Então
A^{*}=\{\,a^{n}\mid n\ge0\} \quad\text{e}\quad A^{*}A=A^{+}=\{\,a^{n}\mid n\ge1\}.
Como \varepsilon=a^{0}\in A^{*} mas \varepsilon\notin A^{+}, temos
A^{*}A\neq A^{*}.

Resposta

A igualdade A^{*}A=A^{*} não é válida em geral; de fato A^{*}A=A^{+}\subsetneq A^{*}.

Exercícios de Livros Relacionados