Convert CFG to PDA (LR)
Definition
How
to Convert CFG to PDA (LR)
We will convert a context free grammar into a pushdown automaton using the SLR(1) parsing method.
The idea behind the conversion from a CFG to an NPDA using the SLR(1) parsing method, is to push terminals from the strings on the stack, pop right-hand sides of productions off the stack, and push their left-hand sides on the stack, until the start variable is on the stack.
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 our 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 (LR). Now, your JFLAP window should look like this :
Just like the conversion to PDA using LL parsing, we need to add transitions between the states. However this time transitions are going to be quite different, because we are using a different parsing method. Still, our goal is to reach state q2. For each terminal, add a loop transition on state q0 that reads the terminal in the input and pushes it on the stack. For each production, add a loop transition on state qo that pops the right side of the production and pushes on the left side of the production from the stack. Therefore, for production “S->aABb”, we would put transition “lambda, bBAa ; S” on state q0. We can convert all the other productions into transitions. After we have successfully completed them, the window will look like :
*NOTE : You can click the production on the left side and click on Create Selected to add the corresponding transition in the PDA.
Now, we have successfully transformed the context-free grammar to a pushdown automaton. We can export this PDA and test it on some inputs and compare it to the original CFG. After exporting the PDA, your new JFLAP window should look like :
Now let's test many strings. Click on Input, then click on Multiple Run. In the Multiple Run window, type input “acb”, “aaaccbcb”, “aa”, “abbbba”, “accb”, “aaccb”, “bcb”. When you click Run Inputs, you might receive a message like this :
Notice that string “acb” is already accepted by PDA. However, when PDA is parsing the string “aaaccbcb”, it generated 674 configurations and still did not achieve the string yet. This does not necessarily mean that the string is impossible to derive. But, it also implies that it could be the case that the string is impossible to derive. So let's press Yes button and see what happens. After clicking Yes to couple of times, you will notice that the string “aaaccbcb” is accepted eventually.
However, this is not always the case. Notice when you reach string “aa”, if you keep clicking on the Yes button, your configurations will get bigger and you will still not achieve the string. In this case, it would be wise not to continue. Select No for this string. After finishing the parsing, your window should look like :
If you run these same inputs on the grammar window using Multiple Run, you will get the same result. Your Multiple Run window should look like this after running :
This concludes our brief tutorial on Converting CFG to PDA (LR). Thanks for reading!