Grammar → PDA

Hopcroft 2e §6.3.1, Thm 6.13. Grammars and pushdown automata define the same languages, and this construction is the easy half: one state, the start symbol on the stack, and the stack thereafter holds exactly the unmatched tail of a leftmost derivation. Run the machine it builds and watch the derivation happen on the stack.

Grammar — one variable per line, alternatives with |, ε for the empty production

Presets:

Symbols split per character (aSb is a, S, b) unless any alternative contains spaces — then tokens are space-separated and id stays one terminal. Variables are whatever appears left of an arrow.

1 variables {S}, 2 terminals {a, b}, start S — 2 productions.

Narration

Enter a string and press Run to step through the machine.