zbMATH — the first resource for mathematics

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

68Q45 Formal languages and automata