If I have an infinite language $L$ which fulfills the Pumping lemma for regular languages, does $L^*$ also fulfill the same conditions?

  • $\begingroup$ 1. if the first word of the Concatenation> n so that we can do a pumping $\endgroup$ – user6885 Feb 16 '13 at 15:30
  • $\begingroup$ 2.word of the Concatenation<n we will Selected her to be V of the lemma and write her meny time we want $\endgroup$ – user6885 Feb 16 '13 at 15:32

In order to show the pumping property of a string like $x_1x_2 \dots x_n$, where each $x_i\in L$ you can distinguish two cases. Either $x_1$ is "short", which means you can pump $x_1$ completely and stay within $L^*$, or $x_1$ is "long" and you can pump "inside" $x_1$.

  • $\begingroup$ Can't you always pump $x_1$ completely, meaning that for every language $L\subseteq \Sigma^*$, $L^*$ satisfies the pumping lemma? $\endgroup$ – Ariel Feb 6 at 19:44
  • $\begingroup$ @Ariel No, consider $\{a^nb^n\mid n\ge 1\}^*$. $\endgroup$ – Hendrik Jan Feb 6 at 19:46
  • $\begingroup$ This language does satisfy the pumping lemma. Actually, any language $L$ for which it holds that $L=L^*$ satisfies the pumping lemma (take the entire word), thus $L^*$ does seem to always satisfy the pumping lemma. $\endgroup$ – Ariel Feb 6 at 19:50
  • 1
    $\begingroup$ Nope. The Pumping Lemma (for regular languages) as I know it, see wikipedia, states that it is possible to find a pumpable segment within the first $p$ symbols of the string, where $p$ is the pumping length. This is not possible for, say $a^pb^p$. If you want to know more, I suggest to start a new question here. $\endgroup$ – Hendrik Jan Feb 6 at 23:30
  • $\begingroup$ My bad, you're obviously correct. $\endgroup$ – Ariel Feb 7 at 6:56

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.