We’ve now seen two pushdown automata for the same language. We saw in the preceding chapter that any language which can be recognised by a finite state automaton can be recognised by a deterministic finite state automaton. Although we haven’t defined Turing machines yet it is true that every language which can be recognised by a Turing machine can be recognised by a deterministic Turing machine. Since pushdown automata are intermediate in power between finite state automata and Turing machines it would seem reasonable to expect that every language which can be recognised by a pushdown automaton can also be recognised by a deterministic pushdown automation. The example considered above lends some support to this expectation, since there’s a natural way to recognise the language with a non-deterministic pushdown automaton but with a certain amount of ingenuity one can also construct a deterministic pushdown automaton for the language. Unfortunately though there are context free languages which cannot be recognised by any deterministic pushdown automaton.