HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
wherelanguageprovethatover

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#98151, answer score: 16

Revisions (0)

No revisions yet.