= Conversion of a context-free grammar to a pushdown automaton
Store the start <nonterminal symbol> on a <stack>. An <epsilon transition> nondeterministically replaces its top <nonterminal symbol> by a <production rule> right-hand side. A top <terminal symbol> can be removed only while consuming the same input symbol. With a protected <stack bottom marker>, enter a final control state when that marker is exposed. Requiring all input to have been read implements <acceptance by final state>. The <stack> records the unprocessed suffix of a <leftmost derivation>, proving equality of the recognized and generated <formal languages>.
Back to article page
