Ogden's lemma for nonterminal bounded languages
R. Boonyavatana, Giora Slutzki · RAIRO - Theoretical Informatics and Applications · 1986
We present an Ogden-type pumping lemma for nonterminal bounded languages.It is shown that these Ogden-type conditions are stronger than the classical-type pumping conditions for nonterminal bounded languages.However, we show that they are not sufficient.In fact, we construct counterexamples at various levels of the Chomsky hierarchy, each of which satisfies the conditions of our Ogden-type lemma.Résumé.-Une grammaire est dite bornée pour les non terminaux si tout mot qui dérive de Paxiome contient un nombre de non terminaux borné par un entier K. On démontre ici un lemme d'itération du type de celui d'Ogden pour les langages engendrés par ces grammaires; ce lemme améliore ceux déjà connus pour ces langages.Nous montrons toutefois qu'il ne constitue pas une condition suffisante en construisant des exemples de langages satisfaisant ce lemme, et pris dans chacune des classes de la hiérarchie de Chomsky.