I should prove that $(A^+)^* = A^*$ in a very formal way, any hints?

  • $\begingroup$ What have you tried so far? Where did you get stuck? Do you have any thoughts? Have you found any examples in your textbook of proving equality of two languages? $\endgroup$ – D.W. Mar 16 '15 at 16:13
  • 1
    $\begingroup$ See cs.stackexchange.com/q/9253/755 and cs.stackexchange.com/q/22540/755 and the dozens of other questions on this site about proving equality of two languages. $\endgroup$ – D.W. Mar 16 '15 at 16:17

When proving $L_1 = L_2$, one common pattern is proving $L_1 \subseteq L_2$ and $L_2 \subseteq L_1$. For proving $L_1 \subseteq L_2$, one common pattern is showing that if $x \in L_1$ then $x \in L_2$. In your case, this means you need to prove two things:

  1. If $x \in (A^+)^*$ then $x \in A^*$.

  2. If $x \in A^*$ then $x \in (A^+)^*$.

Try to use the definitions of $A^*,A^+,(A^+)^*$.

| cite | improve this answer | |

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