# Prove that A** = A*, where A is a language over Σ*

Let $$\mathcal A$$ be an arbitrary language over $$\Sigma^*$$

Proof.

To prove, $$\mathcal A^{**} = \mathcal A^*$$

$$\mathcal A^{**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \right)^*$$ by definition of Kleene Star

My idea is that Kleene star operation distributes over the union of languages but then, I dont know what to do next.

I need some directions.

• It doesn't: $A^* \cup B^* \not= (A \cup B)^*$, in general. – reinierpost Oct 5 '18 at 17:26

Since $$L \subseteq L^*$$ for all $$L$$, we have $$\mathcal{A}^* \subseteq \mathcal{A}^{**}$$. In the other direction, suppose that $$w \in \mathcal{A}^{**}$$. Then there exists an integer $$n \geq 0$$ and words $$x_1,\ldots,x_n \in \mathcal{A}^*$$ such that $$w = x_1 x_2 \ldots x_n$$. Since $$x_i \in \mathcal{A}^*$$, there exists an integer $$m_i$$ such that $$x_i \in \mathcal{A}^{m_i}$$. Thus $$w \in \mathcal{A}^{m_1 + \cdots + m_n} \subseteq \mathcal{A}^*$$, and it follows that $$\mathcal{A}^{**} \subseteq \mathcal{A}^*$$.

Yuval showed a simple way to prove this. Here's an (arguably more complex) alternative based on least fixed points.

The inclusion $$L \subseteq L^*$$ always holds, so $$\mathcal A^* \subseteq \mathcal A^{**}$$.

We are left with proving $$\mathcal A^{**} \subseteq \mathcal A^{*}$$. For this, recall that $$L^*$$ can be defined as the least language such that $$\{\epsilon\} \cup LL^* = L^*$$ Hence, $$\mathcal A^{**}$$ is the least language such that $$\{\epsilon\} \cup \mathcal A^* \mathcal A^{**} = \mathcal A^{**}$$ so, if we prove that $$\mathcal A^*$$ also satisfies the same property, i.e. if we prove $$\{\epsilon\} \cup \mathcal A^* \mathcal A^{*} = \mathcal A^{*} \qquad (*)$$ by the minimality of $$\mathcal A^{**}$$, we will obtain the wanted $$\mathcal A^{**} \subseteq \mathcal A^{*}$$. Proving $$(*)$$ is then trivial.

Depending on what you take as the definition of the Kleene Closure, the proof can be rather trivial. Here is a direct proof from the universal property:

The language $$\mathcal{A}^\ast \subseteq \Sigma^\ast$$ is the smallest submonoid of $$\Sigma^\ast$$ that contains $$\mathcal{A}$$. Likewise, the language $$\mathcal{A}^{\ast\ast}$$ is the smallest submonoid of $$\Sigma^\ast$$ that contains $$\mathcal{A}^\ast$$. Now:

• By definition, $$\mathcal{A}^{\ast\ast}$$ contains $$\mathcal{A}^\ast$$, so $$\mathcal{A}^\ast \subseteq \mathcal{A}^{\ast\ast}$$.
• On the other hand, $$\mathcal{A}^\ast$$ does contain $$\mathcal{A}^\ast$$ and is a monoid, therefore the smallest submonoid containing $$\mathcal{A}^\ast$$ cannot be larger than $$\mathcal{A}^\ast$$, hence $$\mathcal{A}^{\ast\ast} \subseteq \mathcal{A}^\ast$$.

Both inclusions together give equality.