Editing Pushdown automaton (section)

==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.

# <math>(1,\varepsilon,A,1,\alpha)</math> for each rule <math>A\to\alpha</math> (''expand'')
# <math>(1,a,a,1,\varepsilon)</math> for each terminal symbol <math>a</math> (''match'')

The PDA accepts by empty stack. Its initial stack symbol is the grammar's start symbol.<ref>{{Cite web |title=Pushdown Automata |url=https://www.cs.odu.edu/~zeil/cs390/f16/Public/pushdown/index.html |access-date=2024-04-07 |website=www.cs.odu.edu}}</ref>

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.{{sfn|Hopcroft|Ullman|1979|p=115}}

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 <math>M</math> one may construct a context-free grammar <math>G</math> such that {{nobr|<math>N(M)=L(G)</math>.}}{{sfn|Hopcroft|Ullman|1979|p=116}}

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.{{efn|The set of even-length [[Palindrome#Computation theory|palindromes]] of bits can't be recognized by a deterministic PDA, but is a [[context-free language]], with the [[context-free grammar|grammar]] <math>S \rightarrow \epsilon | 0 S 0 | 1 S 1</math>.{{sfn|Hopcroft|Motwani|Ullman|2006|loc=§6.4.3, p. 249}}}} As a consequence, the DPDA is a strictly weaker variant of the PDA. Even for [[regular language]]s, there is a size explosion problem: for any [[General recursive function|recursive function]] <math>f</math> and for arbitrarily large integers <math>n</math>, there is a PDA of size <math>n</math> describing a regular language whose smallest DPDA has at least <math>f(n)</math> states.{{efn|This follows from the quoted [22, Proposition 7] and the stated observation that {{clarify span|any deterministic pushdown automaton can be converted into an equivalent finite automaton|reason=A finite automaton cannot be equivalent to a pushdown automaton, unless the latter doesn't actually use its stack.|date=June 2022}} of at most doubly-exponential size.<ref>{{cite book |last1=Holzer |first1=Markus |last2=Kutrib |first2=Martin |chapter=Non-Recursive Trade-Offs Are "Almost Everywhere" |title=Computing with Foresight and Industry |series=Lecture Notes in Computer Science |date=2019 |volume=11558 |pages=25–36 |doi=10.1007/978-3-030-22996-2_3|isbn=978-3-030-22995-5 }}</ref> }} 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]].{{sfn|Hopcroft and Ullman 1979|p=171}}  A [[linear bounded automaton]] is a device which is more powerful than a pushdown automaton but less so than a Turing machine.{{efn|Linear bounded automata are acceptors for the class of context-sensitive languages,{{sfn|Hopcroft and Ullman 1979|p=225}} which is a proper superclass of the context-free languages, and a proper subclass of Turing-recognizable (i.e. [[recursively enumerable]]) languages.{{sfn|Hopcroft and Ullman 1979|p=228}}}}