Intercalation properties of context-free languages

Context-freedom of a language implies certain intercalation properties known as pumping or iteration lemmas. Although the question of a converse result for some of the properties has been studied, it is still not entirely clear how these properties are related, which are the stronger ones and which are weaker;Among the intercalation properties for context-free languages the better known are the general pumping conditions (generalized Ogden\u27s, Ogden\u27s and classic pumping conditions), Sokolowski-type conditions (Sokolowski\u27s and Extended Sokolowski\u27s conditions) and the Interchange condition. We present a rather systematic investigation of the relationships among these properties; it turns out that the three types of properties, namely pumping, Sokolowski-type and interchange, above are independent. However, the interchange condition is strictly stronger than the Sokolowski\u27s condition;Intercalation properties of some subclasses of context-free languages are also studied. We prove a pumping lemma and an Ogden\u27s lemma for nonterminal bounded languages and show that none of these two conditions is sufficient. We also investigate three of Igarashi\u27s pumping conditions for real-time deterministic context-free languages and show that these conditions are not sufficient either. Furthermore, we formulate linear analogues of the general pumping and interchange conditions and then compare them to the general context-free case. The results show that these conditions are also independent