Converting a NPDA to a Context-Free Grammar


Contents

Introduction
Converting to a Context-Free Grammar
An Exportable Example


Introduction

It is recommended, if you haven't already, to read the tutorial about creating a pushdown automaton, which covers the basics of constructing a NPDA. This section specifically describes how one may transform any nondeterministic pushdown automaton (NPDA) into a context-free grammar by using the tools under the “Convert → Convert to Grammar” menu option. To get started, open JFLAP. Then, either load the file npdaToCfg.jff, or construct the NPDA present in the screen below. When finished, your screen should look something like this:

The idea in the transformation is to convert each transition into one or more productions that mimic the transitions. In some cases, many possible productions are generated in order to generate the equivalent productions, resulting in many useless productions.


Converting to a Grammar

We will now convert this NPDA into a CFG. Click on the “Convert → Convert to Grammar” menu option, and this screen should come up:

It should be noted, before continuing, that in order for JFLAP's conversion algorithm to work, all transitions must pop 1 symbol off the stack and push onto it either 2 or 0 symbols. In addition, there can be only one final state, and any transition into the final state must pop Z off the stack. If you try to proceed to the “Convert → Convert to Grammar” menu option with an invalid state or condition, then an error message will come up. Once all illegal transitions and states have been fixed, JFLAP will proceed to the screen above. Fortunately, our example is a legal candidate for conversion, so we can proceed.

All we need to do to proceed is to click on the specific transitions on our automaton, and all possible grammar rules that can be generated from it will emerge on the right. First, let's add the transitions that pop off an item and then push nothing onto the stack, since they only generate one rule. Click on the last four transitions, and eventually, in the list of rules to the right, you should see some rules resembling this:

Now let's add the last two transitions. First, click on the transition leading from “q0” to “q1”. Instead of just one neat grammar rule, however, we are presented with a large list of grammar rules.

Now, it's possible not every one of these rules will be useful. The correct ones are present, however. The multiplicity of rules is a result of generating with brute force all possible stack combinations. Finally, click on the final transition to add the rules associated with it. When done, your screen may resemble the one below. The highlighted transitions correspond to the selected rules on the right. In order to select a set rule, click on the first or last rule and drag the mouse over the rest in the respective direction.

You may wish to know what the buttons in the toolbar do, since we have not yet used them. The “Hint” button will add the rules of one transition to the list that haven't yet been added. The “Show All” button will add the rules of all remaining transitions to the list. The “What's Left” button will highlight all the transitions that haven't yet been selected. The “Export” button will generate a new context-free grammar using a newly complete rules list in the right panel. However, in the present version of JFLAP, the button will not work for this example because the example generates too many variables. The following is the window that will come up if you try to export the file.


An Exportable Example

Let's now try a file that is exportable. Either load the file npdaToCfg2.jff, or construct the NPDA present in the screen below in a new window. When finished, your screen should look something like this:

You can see, both by examining the NPDA and noticing some of the strings that it accepted or rejected in the list to the left, that the NPDA accepts the language “aaa”. Using the same tools to generate the grammar as before, when finished, you should end up with a list of rules resembling the list on the right:


Sample Automaton Input (from Input → Multiple Run)

Complete List of Rules

Export the file, and you should have roughly the following list of productions. Those productions that generate useless variables that do not lead to anything are never used, although they are generated by the JFLAP algorithm:

Feel free to use the brute force parser on this grammar with the input string “aaa” to see that the string is accepted.

This concludes our brief tutorial on converting NPDAs into context-free grammars. Thanks for reading!