Pumping lemmas for linear and nonlinear context-free languages
Pumping lemmas are created to prove that given languages are not belong to certain
language classes. There are several known pumping lemmas for the whole class and some
special classes of the context-free languages. In this paper we prove new, interesting
pumping lemmas for special linear and context-free language classes. Some of them can be
used to pump regular languages in two place simultaneously. Other lemma can be used to
pump context-free languages in arbitrary many places.
language classes. There are several known pumping lemmas for the whole class and some
special classes of the context-free languages. In this paper we prove new, interesting
pumping lemmas for special linear and context-free language classes. Some of them can be
used to pump regular languages in two place simultaneously. Other lemma can be used to
pump context-free languages in arbitrary many places.
Pumping lemmas are created to prove that given languages are not belong to certain language classes. There are several known pumping lemmas for the whole class and some special classes of the context-free languages. In this paper we prove new, interesting pumping lemmas for special linear and context-free language classes. Some of them can be used to pump regular languages in two place simultaneously. Other lemma can be used to pump context-free languages in arbitrary many places.
arxiv.org