A Grammatical Characterization of One-Way Nondeterministic Stack Languages
- 1 April 1971
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 18 (2) , 148-172
- https://doi.org/10.1145/321637.321639
Abstract
A new family of grammars is introduced. A grammatical characterization of the one-way nondeterministic stack languages is obtained. Characterizations of the languages ac- cepted by nonerasing stack automata and by checking automata are also derived.Keywords
This publication has 6 references indexed in Scilit:
- Nested Stack AutomataJournal of the ACM, 1969
- Checking automata and one-way stack languagesJournal of Computer and System Sciences, 1969
- Indexed Grammars—An Extension of Context-Free GrammarsJournal of the ACM, 1968
- Two-type bracketed grammarsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1968
- One-way stack automataJournal of the ACM, 1967
- Stack automata and compilingJournal of the ACM, 1967