Convert CFG to PDA (LL)


How to Convert CFG to PDA (LL)


We will convert a CFG to a PDA using the LL parsing method.

The idea behind the conversion from a CFG to an equivalent PDA (NPDA in this case) is to derive the productions through the stack. The conversion starts by pushing the start variable on the stack. Whenever there is a variable on the top of the stack, the conversion replaces the variable by its right side, thus applying a production toward deriving the string. Whenever a terminal is on top of the stack and the same symbol is the current input symbol, then the conversion pops the terminal off the stack and processes it as an input symbol. If the stack is emptied, then all the variables were replaced and all the terminals matched, so the string is accepted.

How to Convert CFG to PDA (LL)

We will begin by loading the same grammar that we used for building the LL(1) parse table. You can view that grammar rule in Build LL(1) Parse Table tutorial. (or you can download the file, grammarToLL.jff). After loading the grammar, click on Convert and click Convert CFG to PDA (LL). Now, your JFLAP window should look like this :

We need to add transitions between the states. Our goal is to reach state q2. We have already added the “popped off” loop transitions for matching terminals(the loops on state q1). We must now add the “pushed on” loop transitions on state q1 for each production to get the terminals on the stack. For each production, the left side of the production is popped and the right side of the production is pushed. In this case, we can add the transition from q1 to q1 using “lambda, S : aABb”. This addition successfully portrays our production “S->aABb”.

*NOTE : You can click on the production on the left side and click on Create Selected to add the corresponding transition in the PDA.

After entering all the transitions to the PDA, your JFLAP window should look similar to this :

Now, we have successfully transformed the context-free grammar to a pushdown automaton. We can export this PDA and test it on some inputs to see if the converted PDA accepts the same string as our original CFG. After exporting the PDA, your new JFLAP window should look like :

Now let's run multiple run to test many strings. Click on Input, then click on Multiple Run. In the Multiple Run window, type input “aa”, “aaaccbcb”, “abbbba”, “accb”, “aaccb”, “acb”, “bcb”. In the Grammar window that we have opened for the conversion, click on Input then click on Multiple Brute Force Parse and enter the same strings into the input columns. After running the same inputs on PDA and Brute Force Parser, you should get the result :

Notice that both the PDA and our original grammar accepts/rejects the same strings.

This concludes our brief tutorial on Converting CFG to PDA (LL). Thanks for reading!