Search code examples
context-free-grammarlanguage-theorypushdown-automaton

Program to convert context free language to push down automata?


I can't find any applet or program online to convert a context free language into a push down automata... any help would be greatly appreciated.


Solution

  • It is very easy to do by hand. The PDA has start state s and final state f, the only two states it has. Make a transition ((s, empty, empty),(f, S)), where S is the start symbol of your CFG. For each rule X -> Y, where X is a non terminal symbol and Y is a possibly empty string of terminals and nonterminals, make a transition ((f, empty, X),(f,Y)). Finally, for each terminal symbol a, add the rule ((f, a, a),(f, empty)).

    What this does is start by pushing the start symbol on the stack. Then it replaces any nonterminal it finds at the top of the stack with the right hand side of its production rule, and matches and pops any terminal characters at the top of the stack.