Can the pumping lemma for context free languages be extended to any subword?

Question

It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can perform the usual breakup of $w$ as $w=xyz$ such that $uxy^izv \in L$.

Can we similarly extend the pumping lemma for context-free languages such that it is applicable to any sufficiently long subword? Intuitively I think it should generalize, since the pumping lemma is basically stems from the existence of a repeating non-terminal on some path given a sufficiently deep parse tree, and that should not change if we consider a subword instead of the entire word. But I'm having trouble with formalizing an argument.

If anyone could provide an idea for a formal argument or proof, it would be really appreciated.

Answer 1

The extended form of pumping lemma for regular languages you mentioned is called "the general version of pumping lemma for regular languages".

It is indeed natural to suspect that a similar general version of the usual pumping lemma for context-free languages as said in the title should hold. Unfortunately, it does not. For example, take context-free language $L=\{a^nb^n\}$. The initial subword $a^n$ of $a^nb^n$ can be arbitrarily long. However, no part of that subword can be pumped.

There are, however, a few valid generalizations of the usual pumping lemma for context-free languages. You may want to take a close look at them.

• Ogden's lemma.
• Interchange lemma.

Answer 2

As already remarked, it is not possible to directly generalize the pumping lemma based directly on the length of the strings in the partition $z = uvwxy$.

Ogden's lemma answers your question. Here it is:

• for every CF language $L$
• there exists a constant $n \ge 1$ such that
• for every $z \in L$ with $\|z\| \ge n$
• there exists a decomposition $z = uvwxy$ with $\|vwx\| \le n$, $\|vx\| \ge 1$ such that
• for all $i \ge 0$, $uv^iwx^iy \in L$.

If one reads $\|\cdot\|$ as the length of a string, we have classical pumping. The new Lemma uses "distinguished" or "marked" positions, like we colour some of the letters in the string red. Now $\|\cdot\|$ means the number of marked positions (red symbols) in the string. Thus, we can pump a substring that has at most $n$ marked positions, similar to what you suggest. However, there is no way to avoid some unmarked positions.

The result by Ogden was further extended by Bader and Moura to additionally include a relatively tiny number of "forbidden" positions that could not occur in $vx$, thus are not pumped.

Both results follow the reasoning of the original pumping lemma by Bar-Hillel etal (long paths in the derivation tree must have repeated nonterminals) but the combinatorics is more complicated.