Too many languages satisfy Ogden's Lemma
Marcus Kracht · Scholarly Commons (University of Pennsylvania) · 2004
There are various pumping lemmata for context free languages, the strongest of which is Ogden’s Lemma. It is known that it does not fully characterize context free languages. In an attempt to remedy the situation, Manaster– Ramer, Moshier and Zeitman have strengthened this lemma. As we shall show here, there exist non–semilinear languages that satisfy this stronger lemma and also the lesser known interchange lemma, also due to Ogden. 1