Ogden’s lemma for nonterminal bounded languages. (English) Zbl 0631.68065

Summary: The authors 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, it is shown that they are not sufficient. In fact, the authors construct counterexamples at various levels of the Chomsky hierarchy, each of which satisfies the conditions of our Ogden-type lemma.


68Q45 Formal languages and automata
Full Text: DOI EuDML


[1] 1. A. V. AHO, and J. D. ULLMAN, The Theory of Parsing, Translation, and Compiling, Vol. 1, Prentice-Hall, 1972. MR408321 · Zbl 0264.68032
[2] 2. J. BERSTEL, Transductions and Context-Free Languages, Teubner, Stuttgart 1979. Zbl0424.68040 MR549481 · Zbl 0424.68040
[3] 3. L. BOASSON and S. HORVÁTH, On languages satisfying Ogder’s lemma, RAIRO Informatique Théorique, Vol. 12 (3), 1978, pp. 201-202. Zbl0387.68054 MR510637 · Zbl 0387.68054
[4] 4. R. BOONYAVATANA and G. SLUTZKI, A pumping lemma for Nonterminal Bounded Languages, manuscript, 1984. · Zbl 0631.68065
[5] 5. S. A. GREIBACH, Linearity is Polynomially Decidable for Realtime Pushdown Store Automata, Inform. Contr., Vol. 42, 1979, p. 27-37. Zbl0413.68086 MR538377 · Zbl 0413.68086 · doi:10.1016/S0019-9958(79)90134-7
[6] 6. S. A. GREIBACH, The Unsolvability of the Recognition of Linear Context-Free Languages, JACM, Vol. 13, (4), 1966, pp. 582-587. Zbl0148.00901 MR205770 · Zbl 0148.00901 · doi:10.1145/321356.321365
[7] 7. M. A. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, Reading, Mass., 1978. Zbl0411.68058 MR526397 · Zbl 0411.68058
[8] 8. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory Languages and Computation, Addison-Wesley, Reading, Mass, 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[9] 9. W. OGDEN, A Helpful Result for Proving Inherent Ambiguity. Math. Syst Theory, Vol. 2 (3), pp. 191-194. Zbl0175.27802 MR233645 · Zbl 0175.27802 · doi:10.1007/BF01694004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.