6
$\begingroup$

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.

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

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}^*$.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.