Pushdown automata
John M Howie · 1991
Abstract Before introducing the main ideas of this chapter we shall find it useful to make a slight change in our informal ‘imagery’ concerning finite state automata. At a typical stage qj scans the leftmost square containing aj, deletes aj, changes to gj+1 and moves to scan the new leftmost square.