Pushdown automaton

A machine can use a stack.

A stack is like a pile of trays. You only use the top tray. This helps the machine remember things. It can add a new tray to the top. It can also take the top tray away.

This is called pushing and popping. Some machines only have one choice to make. Others can choose from many paths. These machines help us study how computers work. They can solve many types of puzzles.

A pushdown automaton is a type of machine.

It is used to study what machines can compute. This machine uses a stack to remember things. A stack works like a pile of trays in a cafeteria. You can only work with the tray on top. You can add a new tray to the top. This is called pushing. You can also take the top tray away. This is called popping.

These machines are more powerful than simple machines. Simple machines have no stack to help them. A pushdown automaton can use the top of its stack to make choices. It can also change the stack as it works. Some machines have only one possible move at a time. We call these deterministic pushdown automata. Other machines can choose from many different paths.

These machines can solve special kinds of puzzles. We call these puzzles context-free languages. A machine can also accept a puzzle in two ways. It can reach a final state. Or, it can empty its stack completely.

A pushdown automaton is a special kind of machine used in computer science.

Scientists use these machines to study what can be computed. This machine is more powerful than a simple finite-state machine. A finite-state machine only looks at the current input and its current state. It cannot remember what happened before because it has no extra memory. A pushdown automaton is different because it uses a tool called a stack. This stack acts like a memory for the machine to use.

A stack works much like a pile of trays in a cafeteria. You can only reach the tray at the very top. To add a new item, you perform a pushdown action to put it on top. To remove an item, you pop the top item off. This machine reads a string of symbols from left to right. At each step, it looks at the input symbol and its current state. It also looks at the symbol sitting on top of the stack. Based on these three things, the machine decides its next move. It can change its state, push a new symbol, or pop a symbol.

There are two main ways these machines can behave. A deterministic pushdown automaton, or DPDA, has only one possible move for every situation. This makes it very predictable and useful for designing parsers. A nondeterministic pushdown automaton can have several different possible moves at once. In this case, the machine might follow many different paths. If even one of those paths leads to a successful result, the machine accepts the input. This ability allows it to recognize all context-free languages.

These machines are great at solving puzzles called context-free languages.

A machine can decide if a puzzle is correct in two ways. It can reach a specific final state after reading everything. Or, it can accept by emptying its stack completely. There is a special rule that says these two ways are actually equivalent. This means you can build a machine that uses one way to do the job of the other. This is a helpful fact for mathematicians working with these systems.

We can also compare these machines to even more powerful tools. A Turing machine is much stronger than a pushdown automaton. A Turing machine can move back and forth on its memory and change things. A pushdown automaton is weaker because popping an item removes that data forever. However, if you give a pushdown automaton two stacks, it becomes just as powerful as a Turing machine. By using two stacks, the machine can save the data it would otherwise lose. This shows how adding just one more tool can change everything.

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.