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.
\left(A^{*}\right)^{*}=A^{*}

Passo 1

O enunciado diz que A\subseteq V^* é uma linguagem sobre o alfabeto V. A tarefa é mostrar que a operação de Kleene star é idempotente, ou seja,
\bigl(A^*\bigr)^* \;=\; A^*.
Para isso, vamos usar a definição de estrela de Kleene como união de potências e as propriedades de fechamento de concatenção.

Passo 2

Lembremos a definição de estrela de Kleene para qualquer linguagem L:
L^* \;=\;\bigcup_{n=0}^{\infty} L^n,
onde
L^0 = \{\varepsilon\}, \quad L^{n+1} = L^n \cdot L
e “ \cdot” é a operação de concatenação de linguagens. Em particular,
A^* = \bigcup_{n=0}^{\infty} A^n.

Passo 3

Mostramos primeiro que
A^* \;\subseteq\;\bigl(A^*\bigr)^*.
De fato, observe que
A^* = \bigl(A^*\bigr)^1
e \bigl(A^*\bigr)^1 é um dos termos da união
\bigl(A^*\bigr)^* = \bigcup_{m=0}^\infty \bigl(A^*\bigr)^m.
Logo todo elemento de A^* aparece em \bigl(A^*\bigr)^*, e temos a inclusão desejada.

Passo 4

Agora mostramos que
\bigl(A^*\bigr)^* \;\subseteq\; A^*.
Seja w\in\bigl(A^*\bigr)^*. Então existe algum m\ge0 tal que
w \in \bigl(A^*\bigr)^m = \underbrace{A^* \cdot A^* \cdots A^*}_{m\text{ fatores}}.
Isto significa que w = w_1 w_2 \cdots w_m com cada w_i\in A^*. Mas cada w_i é concatenação de algum número finito de palavras de A. Suponha
w_i = a_{i,1} a_{i,2}\cdots a_{i,n_i},
onde cada a_{i,j}\in A. Então
w = a_{1,1}a_{1,2}\cdots a_{1,n_1}\; a_{2,1}\cdots a_{2,n_2}\;\cdots\; a_{m,1}\cdots a_{m,n_m},
que é exatamente uma concatenação finita de elementos de A. Por definição, isso mostra que w\in A^*. Assim \bigl(A^*\bigr)^*\subseteq A^*.

Passo 5

Como mostramos ambas as inclusões
A^* \subseteq \bigl(A^*\bigr)^* \quad\text{e}\quad \bigl(A^*\bigr)^* \subseteq A^*,
concluímos que
\bigl(A^*\bigr)^* = A^*.

Resposta

\displaystyle (A^*)^* = A^*, ou seja, a operação de Kleene star é idempotente.

Exercícios de Livros Relacionados