Intercalation properties of context-free languages

Abstract

<p>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's, Ogden's and classic pumping conditions), Sokolowski-type conditions (Sokolowski's and Extended Sokolowski's 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's condition;Intercalation properties of some subclasses of context-free languages are also studied. We prove a pumping lemma and an Ogden's lemma for nonterminal bounded languages and show that none of these two conditions is sufficient. We also investigate three of Igarashi's 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.</p>