0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 1. if the first word of the Concatenation> n so that we can do a pumping $\endgroup$
    – user6885
    Feb 16, 2013 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, 2013 at 15:32

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
5
  • $\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, 2019 at 19:44
  • $\begingroup$ @Ariel No, consider $\{a^nb^n\mid n\ge 1\}^*$. $\endgroup$ Feb 6, 2019 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, 2019 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$ Feb 6, 2019 at 23:30
  • $\begingroup$ My bad, you're obviously correct. $\endgroup$
    – Ariel
    Feb 7, 2019 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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