Pushdown automaton

In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a special kind of machine that uses a stack.

Pushdown automata help us learn about what problems computers and other machines can solve.

They are stronger than finite-state machines but weaker than Turing machines. This means they can solve harder problems than some machines, but not as many as others.

Deterministic pushdown automata can understand all deterministic context-free languages, while nondeterministic ones can understand all context-free languages. These ideas are used when making parsers, tools that help computers read and work with human languages and programming languages.

The word "pushdown" describes how the stack works, like a cafeteria tray dispenser where you can only reach the top tray. This is unlike a stack automaton, which can reach deeper trays. There are even more advanced types, like a nested stack automaton, which can manage even more difficult 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 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. For example, a PDA can check 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 help it track 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 changed into a special machine called a pushdown automaton. This machine uses a stack to follow the rules of the grammar. When the grammar tells it to change a letter, the machine takes the top letter from its stack and puts new letters in its place. When the grammar tells it to use a real letter, the machine checks that letter against the next one in the input.

There is a special type of pushdown automaton called a deterministic pushdown automaton. This type can only follow one path at a time. Not all context-free languages can use this type, which shows that deterministic pushdown automata are simpler and not as powerful as other kinds.

Turing machines

A pushdown automaton (PDA) is like a special kind of Turing Machine (TM). It has two tapes with some limits. On the first tape, the TM can only read the input and move from left to right. It cannot change anything. 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. 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 helps the PDA keep track of more information and do any Turing Machine operation.

Generalization

A generalized pushdown automaton (GPDA) is a special kind of machine. It can write or remove many 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. This means they have the same computing power. We can show this by breaking down the actions of a GPDA into smaller steps. A regular pushdown automaton can follow these steps.

Stack automata

Stack automata are a special kind of machine related to pushdown automata. They were studied by researchers in 1967. These machines can move both left and right along the input they are reading.

They can also move up and down through a stack, but they never remove information from the stack.

Some types of stack automata can recognize more complex sets of instructions than other machines. These include 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.