Pushdown automaton

In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack. Pushdown automata are important because they help us understand what kinds of problems can be solved by computers and other machines.

Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines. This means they can solve more complex problems than some machines, but not as many as others.

Deterministic pushdown automata can recognize all deterministic context-free languages, while nondeterministic ones can recognize all context-free languages. These ideas are often used in designing parsers, which are tools that help computers understand and process human languages and programming languages.

The term "pushdown" refers to how the stack works, like a tray dispenser at a cafeteria, where you can only access the top item. This is different from a stack automaton, which can work with deeper items in the stack. There are even more advanced types, like a nested stack automaton, which can handle even more complex tasks.

Informal description

A finite-state machine can only look at the current input and state, without remembering past inputs. A pushdown automaton (PDA) is different because it uses a stack to help remember important information.

As the PDA reads input from left to right, it can look at the current input, its current state, and the top symbol on the stack to decide what to do next. It can add a new symbol to the top of the stack or remove the top symbol, depending on the rules it follows. If there is only one possible action at each step, the PDA is called a deterministic pushdown automaton (DPDA). If there are many possible actions, it is called a general or nondeterministic PDA.

Formal definition

A pushdown automaton (PDA) is a special type of machine used in computer science. It has several parts:

• A finite set of states — these are like different modes the machine can be in.
• An input alphabet — the symbols it can read from its input.
• A stack alphabet — the symbols it can store on its stack.
• A transition relation — rules that tell the machine what to do next.
• A start state — where the machine begins.
• An initial stack symbol — the first symbol placed on the stack.
• A set of accepting states — states that mean the machine has successfully processed the input.

The PDA can read a symbol, change its state, and add or remove symbols from the stack all in one step. This makes it more powerful than a simple state machine but less powerful than a Turing machine.

Pushdown automata help us understand what kinds of problems can be solved by machines with limited memory.

Example

A pushdown automaton (PDA) can recognize certain patterns of symbols. One example is a PDA that checks if a string has the same number of 0s followed by the same number of 1s, like "001" or "000111".

The PDA uses a stack to keep track of the symbols it reads. When it sees a 0, it adds a special symbol "A" to the stack. When it sees a 1, it removes an "A" from the stack. If the stack is empty and only the end marker "Z" remains when the input ends, the PDA accepts the string. This shows how a PDA can use a stack to match patterns in the input.

Context-free languages

Every context-free grammar can be turned into a special kind of machine called a pushdown automaton. This machine uses a stack to help it follow the rules of the grammar. When the grammar says to change a letter, the machine takes the top letter from its stack and replaces it with new letters. When the grammar says to use a real letter from the alphabet, the machine checks that letter against the next one in the input.

There is a special kind of pushdown automaton called a deterministic pushdown automaton, which can only follow one path at a time. Not all context-free languages can be handled this way, showing that deterministic pushdown automata are a simpler, less powerful type of machine.

Turing machines

A pushdown automaton (PDA) is similar to a special kind of Turing Machine (TM) that has two tapes with certain limits. On the first tape, the TM can only read the input and move from left to right without making changes. On the second tape, it can only add to or remove from a stack of data.

A PDA is weaker than a full Turing Machine because when it removes data (pops), that information is lost. To make a PDA as powerful as a TM, we can use two stacks instead of one. This allows the PDA to keep track of more information and simulate any Turing Machine operation.

Generalization

A generalized pushdown automaton (GPDA) is a special kind of machine that can write or remove whole strings of symbols at once from its stack, instead of just one symbol at a time.

Both regular pushdown automata and generalized pushdown automata can recognize the same set of languages, meaning they have the same computing power. This can be shown through a step-by-step process that breaks down the actions of a GPDA into a series of smaller steps that a regular pushdown automaton can follow.

Stack automata

Stack automata are a more advanced type of machine related to pushdown automata. They were studied by researchers in 1967 and can move both left and right along the input they are reading. These machines can also move up and down through a stack but only in a way that does not remove information from the stack.

Certain types of stack automata can recognize more complex sets of instructions than other machines, including a group known as context-sensitive languages.

Alternating pushdown automata

An alternating pushdown automaton (APDA) is a special kind of pushdown automaton. It has two types of states: existential and universal. In an existential state, the automaton can choose different paths and will accept if at least one path works out. In a universal state, it must follow all possible paths and will only accept if every path works out.

This idea was first introduced by Chandra, Kozen, and Stockmeyer. Later, it was shown that alternating pushdown automata can solve problems that need exponential time to compute.