A Formalization of Transition Diagram Systems
- 1 April 1973
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 20 (2) , 235-257
- https://doi.org/10.1145/321752.321756
Abstract
The transition diagram systems first introduced by Conway are formalized in terms of a restricted deterministic pushdown acceptor (DPDA) called a nested DPDA. It is then established that the class of nested DPDA's is capable of accepting all deterministic context-free languages. The proof of this involves demonstrating that left recursion can be eliminated from deterministic (or LR( k )) grammars without destroying the deterministic property. Using various structural properties of nested DPDA's, one can then establish equivalence results for certain classes of deterministic languages.Keywords
This publication has 4 references indexed in Scilit:
- A practical method for constructing LR ( k ) processorsCommunications of the ACM, 1969
- On the translation of languages from left to rightInformation and Control, 1965
- A New Normal-Form Theorem for Context-Free Phrase Structure GrammarsJournal of the ACM, 1965
- Design of a separable transition-diagram compilerCommunications of the ACM, 1963