I am trying to prove this expression but don't have an exact idea about what to do:

If $E$ is any alphabet and $L$ is any language $L \subseteq E^*$. Prove that $L^*L^* = L^*$.


closed as unclear what you're asking by D.W., David Richerby, vonbrand, Juho, Artem Kaznatcheev Mar 27 '14 at 7:54

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What have you tried? This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – D.W. Mar 12 '14 at 17:02

The standard approach to such proofs is:

  1. Let $w \in L^*L^*$. This implies [...] and thus $w \in L^*$.
  2. Let $w \in L^*$. This implies [...] and thus $w \in L^*L^*$.

Both parts combined give the proof of your statement. Does this help?

  • $\begingroup$ Thank you! Just one thing, how can i show that w ∈ LL? $\endgroup$ – hebele Mar 12 '14 at 11:18
  • $\begingroup$ @Ezgi In the second part? Note that $w$ is the same as $w$ concatenated with the empty word. $\endgroup$ – FrankW Mar 12 '14 at 11:22

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