patternMinor
Can the pumping lemma for context free languages be extended to any subword?
Viewed 0 times
canthefreelanguagesanyextendedpumpingforlemmacontext
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#104726, answer score: 4
Revisions (0)
No revisions yet.