If I have an infinite language $L$ which fulfills the Pumping lemma for regular languages, does $L^*$ also fulfill the same conditions?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 1. if the first word of the Concatenation> n so that we can do a pumping $\endgroup$– user6885Feb 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$– user6885Feb 16, 2013 at 15:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$.
answered Feb 16, 2013 at 13:06
-
$\begingroup$ Can't you always pump $x_1$ completely, meaning that for every language $L\subseteq \Sigma^*$, $L^*$ satisfies the pumping lemma? $\endgroup$– ArielFeb 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$– ArielFeb 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
-