1
$\begingroup$

I do not understand the proof for this. I know that every word in $(A^*)^*$ is made up of words from $A^*$, and that this is made up from words in $A$. But how does this help with showing that $(A^*)^*$ is a subset of $A^*$.

$\endgroup$
  • $\begingroup$ Have you tried applying the definition of the Kleene star on both sides? $\endgroup$ – Raphael Aug 26 '13 at 8:28
4
$\begingroup$

Knowing that $A$ is regular is not relevant.

Hint. Just replace "made up of words of $A^*$" by "is a concatenation of words of $A^*$" in your sentence and you will have the answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry but this still just doesn't make sense to me. How does knowing that A** is a concatenation of words of A* tell me that A** is a subset of A*? $\endgroup$ – user678392 Aug 25 '13 at 13:41
2
$\begingroup$

A concatenation of words of $A^*$ gives a word which is in $A^*$, because of the very definition of $A^*$. This gives the result.

Moreover, one can prove that $^*$ is a closure operator, which includes this property.

| cite | improve this answer | |
$\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.