Pushdown Automaton

A pushdown automaton is a state machine extended with a stack — an unbounded last-in, first-out memory. At each step the PDA reads an input symbol (or takes an ε-move), pops the top stack symbol, and depending on all three it transitions to a new state and pushes zero or more symbols onto the stack. PDAs recognise exactly the context-free languages.

This simulator uses acceptance by final state: a string is accepted if, after consuming all input, the PDA is in one of the designated accept states (the stack contents do not matter). Acceptance by empty stack is an equivalent model — every language accepted one way can be accepted the other — but final-state acceptance is more common in practice.

An ε-transition lets the PDA change state, pop a stack symbol, and push new symbols without consuming any input character. This simulator tries ε-transitions before reading the next input symbol and detects cycles to prevent infinite ε-loops.

The label "a,A/BC" means: read input "a", pop "A" from the top of the stack, and push "BC" with "B" becoming the new top. An empty push (written ε) means pop only. The left-most character in the push string is pushed last, so it ends up on top.

PDAs recognise all context-free languages, which properly include the regular languages. Classic examples that need a stack are {aⁿbⁿ | n ≥ 1} (equal numbers of a and b) and balanced parentheses. However, PDAs cannot recognise all languages — {aⁿbⁿcⁿ} for example requires a Turing machine.

Yes — PDAs and CFGs are exactly equivalent in expressive power. For every CFG there is a PDA that accepts the same language, and vice versa. This equivalence is fundamental: it means you can freely switch between the grammar description (production rules) and the machine description (states + stack) when reasoning about context-free languages.

No. Every language recognised by a DFA or NFA is also recognised by a PDA (since regular languages are a subset of context-free languages), but the reverse is not true. A PDA can recognise {aⁿbⁿ} and balanced parentheses, which no DFA or NFA can. The stack gives PDAs strictly more memory than the finite-state control of a DFA/NFA.

No — a Turing machine is strictly more powerful. A Turing machine has an unbounded read/write tape it can traverse in both directions, whereas a PDA only has a stack (last-in, first-out). Languages like {aⁿbⁿcⁿ} are beyond any PDA but are decidable by a Turing machine. Turing machines can compute anything that is algorithmically computable; PDAs are limited to the context-free languages.