patternModerate
Prove that A** = A*, where A is a language over Σ*
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.
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.