Definition
Pushdown Automaton Criterion
A Turing machine satisfies the pushdown automaton criterion if
- on the input tape it can nevver move to the left, and
- for the read/write head on the work tape, in every configuration it holds that:
- to the left of the head there can only be non-blank symbols, and
- to the right of the head there can only be blank symbols
The machines behaves like a stack.
todo convert to pushdown automaton eventually