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.