structural:summarization, quality:correction, structural:reformatting
Context-free languages

Every context-free grammar can be transformed into an equivalent nondeterministic pushdown automaton. The derivation process of the grammar is simulated in a leftmost way. Where the grammar rewrites a nonterminal, the PDA takes the topmost nonterminal from its stack and replaces it by the right-hand part of a grammatical rule (expand). Where the grammar generates a terminal symbol, the PDA reads a symbol from input when it is the topmost symbol on the stack (match). In a sense the stack of the PDA contains the unprocessed data of the grammar, corresponding to a pre-order traversal of a derivation tree.

Technically, given a context-free grammar, the PDA has a single state, 1, and its transition relation is constructed as follows.

The PDA accepts by empty stack. Its initial stack symbol is the grammar's start symbol.

For a context-free grammar in Greibach normal form, defining (1,γ) ∈ δ(1, a, A) for each grammar rule A → a γ also yields an equivalent nondeterministic pushdown automaton.

The converse, finding a grammar for a given PDA, is not that easy. The trick is to code two states of the PDA into the nonterminals of the grammar.

Theorem. For each pushdown automaton M {\displaystyle M} one may construct a context-free grammar G {\displaystyle G} such that N (M) = L (G) {\displaystyle N(M)=L(G)}.

The language of strings accepted by a deterministic pushdown automaton (DPDA) is called a deterministic context-free language. Not all context-free languages are deterministic. As a consequence, the DPDA is a strictly weaker variant of the PDA. Even for regular languages, there is a size explosion problem: for any recursive function f {\displaystyle f} and for arbitrarily large integers n {\displaystyle n}, there is a PDA of size n {\displaystyle n} describing a regular language whose smallest DPDA has at least f (n) {\displaystyle f(n)} states. For many non-regular PDAs, any equivalent DPDA would require an unbounded number of states.

A finite automaton with access to two stacks is a more powerful device, equivalent in power to a Turing machine. A linear bounded automaton is a device which is more powerful than a pushdown automaton but less so than a Turing machine.