Mostre que estas igualdades são válidas.
\left(A^{*}\right)^{*}=A^{*} para todo conjunto A de seqüências.

Passo 1

O enunciado pede para mostrar que, para todo conjunto A\subseteq\Sigma^* (onde \Sigma é um alfabeto e \Sigma^* o conjunto de todas as cadeias finitas), vale a igualdade
(A^*)^* \;=\; A^*.
Aqui o conteúdo é a operação Kleene star em teoria de linguagens formais, que gera todas as concatenações finitas de cadeias de um dado conjunto.

Passo 2

Mostramos primeiro (A^*)^*\subseteq A^*. Seja x\in (A^*)^*. Por definição de estrela, existem n\ge1 e cadeias
w_1,\,w_2,\,\dots,\,w_n\in A^*
tais que
x \;=\; w_1\,w_2\cdots w_n.
Cada w_i\in A^* é, por sua vez, concatenação finita de cadeias de A. Ou seja, para cada i existe k_i\ge0 e
a_{i1},a_{i2},\dots,a_{i\,k_i}\in A \quad\text{com}\quad w_i = a_{i1}a_{i2}\cdots a_{i\,k_i}.
Logo
x \;=\; \bigl(a_{11}a_{12}\cdots a_{1k_1}\bigr) \bigl(a_{21}\cdots a_{2k_2}\bigr)\cdots \bigl(a_{n1}\cdots a_{n\,k_n}\bigr),
que é uma concatenação finita de cadeias em A. Assim x\in A^*. Concluímos (A^*)^*\subseteq A^*.

Passo 3

Agora mostramos A^*\subseteq (A^*)^*. Seja x\in A^*. Então, por definição, x é uma concatenação finita de cadeias em A. Mas também isso significa que x é (trivialmente) concatenação de um único elemento de A^*, a saber de si próprio. Portanto x pode ser visto como
x = w_1\quad\text{com}\quad w_1 = x\in A^*,
logo x\in (A^*)^*. Assim A^*\subseteq (A^*)^*.

Resposta

(A^*)^* = A^*.

Exercícios de Livros Relacionados