A note on pushdown store automata and regular systems
Sheila A. Greibach · Proceedings of the American Mathematical Society · 1967
Recent work on pushdown store automata has focused attention on various sets of pushdown store tapes [8].Certain sets of tapes associated with pushdown store automata can be proved regular.As a consequence we obtain a new proof of a theorem due to Biichi:2 that regular canonical systems (i.e., productions of the form aQ->fiQ) produce regular sets [2].3In this paper we shall use a theorem of Bar-Hillel, Pedes and Shamir [l] to show that the set of tapes left on the pushdown store by a regular set is regular,4 and derive Btichi's theorem from that result.First we shall need some definitions.We assume familiarity with the definition of production systems.6Definition.A finite state grammar is a quadruple G= (I, T, X, P), where / and P are finite sets, If\T = 0, X(£I and P is a finite set of semi-Thue productions of the forms QiZQ2-^QiaYQ2, QiZQ2-+QiaQ2, Z, Y G /, a G TV {\\.A set L is regular iff L= (wGP*|X=>*w\ for some finite state grammar G.6We must now define pushdown store automata and their actions.