Drawtomata / CFG to PDA converter
CFG to PDA converter
Type a grammar above. Drawtomata builds an equivalent NPDA, lets you run it on any string with instantaneous descriptions, and converts an NPDA back to a context-free grammar with the [qᵢ A qⱼ] construction.
Grammar to NPDA
If the grammar is in Greibach normal form, every production A → aX₁…Xₖ becomes one move: read a, pop A, push X₁…Xₖ. Otherwise the general method uses λ-moves to expand variables on the stack and plain moves to match terminals.
NPDA to grammar
The NPDA is first brought into a form where every move pops one symbol and pushes zero or two. Then the variable [qᵢ A qⱼ] stands for “go from qᵢ to qⱼ while popping A”, and each move gives productions. Useless productions are removed, and the grammar is checked against the NPDA on all short strings.
Also on the same tab: leftmost and rightmost derivations, parse trees and a bounded ambiguity search. Grammar simplification and Chomsky normal form are on the parsing tab.