2
$\begingroup$

The pumping lemma states that if we can split a string w (taken from a context-free language L) as uvxyz with conditions |vy|>=1 |vxy|<=p |w|>=p for some p then $uv^ixy^iz$ is in L for any i.

However, some context-free languages include the empty string, which has length 0. How can we possibly split the empty string to satisfy the condition |vy|>=1?

For instance, the following language $\{0^n1^n0^n1^n|n>=0 \} $ contains the empty string but is not context-free, so how can I ensure a string taken from it can we split as uvxyz with |vy|>=1?

Thanks!

$\endgroup$

1 Answer 1

2
$\begingroup$

The pumping lemma requires the word $w$ you start with to be large enough — larger than the pumping lemma constant $p$.

However, this doesn't really answer your question, which is how to ensure that the string given to the pumping lemma is not empty. Here you are very lucky — you are the one choosing the string! The pumping lemma only states that whatever string $w$ you choose from the language (as long as it is long enough), it can be decomposed as $w = uvxyz$ so that $uv^ixy^iz$ is in the language for all $i \geq 0$, $vy \neq \epsilon$, and $|vxy| \leq p$.

$\endgroup$

Your Answer

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

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