Ogden's lemma for nonterminal bounded languages

R. Boonyavatana; G. Slutzki

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1986)

  • Volume: 20, Issue: 4, page 457-471
  • ISSN: 0988-3754

How to cite

top

Boonyavatana, R., and Slutzki, G.. "Ogden's lemma for nonterminal bounded languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 20.4 (1986): 457-471. <http://eudml.org/doc/92271>.

@article{Boonyavatana1986,
author = {Boonyavatana, R., Slutzki, G.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {context-free grammar; pumping lemma; nonterminal bounded languages; Chomsky hierarchy},
language = {eng},
number = {4},
pages = {457-471},
publisher = {EDP-Sciences},
title = {Ogden's lemma for nonterminal bounded languages},
url = {http://eudml.org/doc/92271},
volume = {20},
year = {1986},
}

TY - JOUR
AU - Boonyavatana, R.
AU - Slutzki, G.
TI - Ogden's lemma for nonterminal bounded languages
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1986
PB - EDP-Sciences
VL - 20
IS - 4
SP - 457
EP - 471
LA - eng
KW - context-free grammar; pumping lemma; nonterminal bounded languages; Chomsky hierarchy
UR - http://eudml.org/doc/92271
ER -

References

top
  1. 1. A. V. AHO, and J. D. ULLMAN, The Theory of Parsing, Translation, and Compiling, Vol. 1, Prentice-Hall, 1972. Zbl0264.68032MR408321
  2. 2. J. BERSTEL, Transductions and Context-Free Languages, Teubner, Stuttgart 1979. Zbl0424.68040MR549481
  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.68054MR510637
  4. 4. R. BOONYAVATANA and G. SLUTZKI, A pumping lemma for Nonterminal Bounded Languages, manuscript, 1984. Zbl0631.68065
  5. 5. S. A. GREIBACH, Linearity is Polynomially Decidable for Realtime Pushdown Store Automata, Inform. Contr., Vol. 42, 1979, p. 27-37. Zbl0413.68086MR538377
  6. 6. S. A. GREIBACH, The Unsolvability of the Recognition of Linear Context-Free Languages, JACM, Vol. 13, (4), 1966, pp. 582-587. Zbl0148.00901MR205770
  7. 7. M. A. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, Reading, Mass., 1978. Zbl0411.68058MR526397
  8. 8. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory Languages and Computation, Addison-Wesley, Reading, Mass, 1979. Zbl0426.68001MR645539
  9. 9. W. OGDEN, A Helpful Result for Proving Inherent Ambiguity. Math. Syst Theory, Vol. 2 (3), pp. 191-194. Zbl0175.27802MR233645

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.