Pushdown automaton

In the theory of computation, a pushdown automaton (PDA) is a mathematical model of a machine.

These machines are essential tools in theoretical computer science. Scientists use them to study the limits of what can be computed. A PDA is more capable than a finite-state machine. However, it is less capable than a Turing machine. While a finite-state machine only considers the current input and its state, a PDA possesses an additional memory component. This component is called a stack.

The stack operates like a tray dispenser in a cafeteria. You can only interact with the item at the very top. The term "pushdown" describes this specific restriction. You can add a symbol to the top, which is called a push. You can remove the top symbol, which is called a pop. You can also choose to leave the stack unchanged. Unlike a stack automaton, a PDA cannot access or manipulate deeper elements in the pile. This focus on the top element defines its specific mechanical behavior.

A PDA processes an input string from left to right. To decide its next move, the machine looks at three specific pieces of information. First, it checks the current input symbol. Second, it identifies its current state. Third, it examines the symbol at the top of the stack. Based on these three factors, the machine follows a transition. This transition allows it to change its state and manipulate the stack. The machine can push a new symbol, pop the existing one, or do nothing to the stack.

There are two primary types of pushdown automata based on their decision-making. A deterministic pushdown automaton (DPDA) is a machine where only one transition is possible for any given situation. These are highly predictable and are often used in parser design. A nondeterministic PDA is more general. In a nondeterministic machine, several different actions might be possible at once. A string is considered accepted if at least one possible sequence of steps leads to an accepting configuration.

Mathematically, a PDA is defined as a 7-tuple. This formal structure includes a set of states, an input alphabet, and a stack alphabet. It also includes a transition relation, a start state, an initial stack symbol, and a set of accepting states. There are two ways a machine can accept a string. It can accept by final state, meaning it reaches a specific state in its set of accepting states. Alternatively, it can accept by empty stack, meaning the stack is completely cleared. Interestingly, these two modes are equivalent. For every PDA that accepts by final state, one can be constructed that accepts by empty stack, and vice versa.

Pushdown automata are closely linked to context-free languages. In fact, every context-free grammar can be transformed into an equivalent nondeterministic PDA. The machine simulates the grammar by using the stack to hold unprocessed data. When the grammar rewrites a nonterminal, the PDA expands it by replacing the top stack symbol with new symbols. When the grammar generates a terminal symbol, the PDA matches it against the input.

While nondeterministic PDAs recognize all context-free languages, DPDAs are more limited. They only recognize a subset called deterministic context-free languages.

We can also compare the PDA to the Turing machine. A Turing machine is a much more powerful model of computation. A PDA is considered a restricted Turing machine with two tapes. On one tape, the machine reads input from left to right. On the second tape, it can only push or pop data. The PDA is weaker because the pop operation deletes data forever. However, adding a second stack changes the machine's power entirely. A PDA with two stacks can simulate a full Turing machine by using one stack to move right and the other to move left. This shows how even small changes in memory access can fundamentally alter computational capability.