A Formalization of Transition Diagram Systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Formalization of Transition Diagram Systems

Full text

Pdf (1.49 MB)

Source

Journal of the ACM (JACM) archive
Volume 20 , Issue 2 (April 1973) table of contents

Pages: 235 - 257

Year of Publication: 1973

ISSN:0004-5411

Author

David Bruce Lomet

IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 9

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321752.321756 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Melvin E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, v.6 n.7, p.396-408, July 1963 [doi>10.1145/366663.366704]
	2	Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
	3	Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the ACM (JACM), v.12 n.1, p.42-52, Jan. 1965 [doi>10.1145/321250.321254]
	4	GRIFFIT~S, M. AnMyse determiaiste et Compilateurs. Ph.D. dies., U. of Grenoble (Oct. 1969).
	5	KN~T~I, D.E. On the translation of languages from left to right. I~$orm. Contr. 8 (Oct. 1965), 607-639.
	6	A. J. Korenjak, A practical method for constructing LR (k) processors, Communications of the ACM, v.12 n.11, p.613-623, Nov. 1969 [doi>10.1145/363269.363281]
	7	David Bruce Lomet, The construction of efficient deterministic language processors, 1969
	8	D. J. Rosenkrantz , R. E. Stearns, Properties of deterministic top down grammars, Proceedings of the first annual ACM symposium on Theory of computing, p.165-180, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805431]
	9	TIXXER, V. Recursive functions of regular expressions in language analysis. Tech. Rep. CS-58, Comput. Sci. Dep., Stanford U., Stanford, Calif., March 1967.

CITED BY 9

	Neil D. Jones , Steven S. Muchnick, The Complexity of Finite Memory Programs with Recursion, Journal of the ACM (JACM), v.25 n.2, p.312-231, April 1978
	S. Ron Oliver , Nell D. Jones, Program control via transition matrices—a novel application of micro-programming, ACM SIGPLAN Notices, v.11 n.4, p.70-77, April 1976
	Michael Hammer, A new grammatical transformation into LL(k) form (Extended Abstract), Proceedings of the sixth annual ACM symposium on Theory of computing, p.266-275, April 30-May 02, 1974, Seattle, Washington, United States
	A. Ron Oliver , Neil D. Jones, Program control via transition matrices: a novel application of micro-programming, ACM SIGMICRO Newsletter, v.7 n.1, p.8-27, March 1976
	Thomas R. Wilcox , Alan M. Davis , Michael H. Tindall, The design and implementation of a table driven, interactive diagnostic programming system, Communications of the ACM, v.19 n.11, p.609-616, Nov. 1976
	João José Neto, Adaptive automata for context-dependent languages, ACM SIGPLAN Notices, v.29 n.9, p.115-124, Sept. 1994
	C. Raymond Perrault, Intercalation theorems for tree transducer languages, Proceedings of seventh annual ACM symposium on Theory of computing, p.126-136, May 05-07, 1975, Albuquerque, New Mexico, United States
	David Hemmendinger, Specifying Ada Server Tasks with Executable Formal Grammars, IEEE Transactions on Software Engineering, v.16 n.7, p.741-754, July 1990
	Mark Green, A survey of three dialogue models, ACM Transactions on Graphics (TOG), v.5 n.3, p.244-275, July 1986