More pushdown automata

We can similarly consider the input to a pushdown automaton as as a separate stack which, unlike its working stack, is read-only, i.e. allows only pop operations and not push operations.

Every finite state automaton is a pushdown automaton, specifically a pushdown automaton which doesn’t ever touch its working stack, so anything we can do with a finite state automaton can be done with a pushdown automaton. The converse is not true. We’ve already seen that every context free language is recognised by a pushdown automaton and that every finite state automaton recognises a regular language. If every pushdown automaton could be simulated with a finite state automaton then every context free language would be regular, but we’ve already seen that this is not true. The language of balanced parentheses, for example, is context free but not regular.

As with finite state automata we could consider instead a version where the other stack is write-only, so the automaton has no input but has an output. Again this is uninteresting if we restrict ourselves to deterministic automata but if we allow non-deterministic automata we get something useful. In fact the languages which can be sets of outputs of such a machine is exactly the context free languages. Arguably this is a more intuitive way to think of the connection between languages and grammars since our generative grammar is used to construct an actually generator rather than a recogniser.