A Formalization of Transition Diagram Systems

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

• 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Documentation, Languages, Management, Measurement, Performance, Theory