Converting a DFA to a Regular Grammar

Contents

Introduction
Converting to a Regular Grammar

Introduction

The reader, if he or she hasn't already, should read the tutorial about creating a finite automaton, which covers the basics of constructing a FA and describes how they are implemented in JFLAP. This section specifically describes how one may transform one of these finite automata into a right-linear grammar.

To get started, open JFLAP. Then, either load the file dfaToRegGrammar.jff, or construct the nondeterministic finite automaton present in the screen below. When finished, your screen should look something like this:

Converting to a Regular Grammar

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

Notice the labels on the states in the picture. JFLAP, by default, assigns unique variables to each state. Each transition in the graph corresponds with a production in a right-linear grammar. For example, the transition from “q0” to “q0” along the transition “a” matches the production “S → aS”. Let's add this production to our list of productions in the right panel. To add the production, just click on the “a” transition on state “q0”. The “a” transition should now be highlighted in red, and the production added to the right panel.

Now, let's see what our next step might be. We know it probably will be a transition in the FA, but if we are having trouble, we can click on the “Hint” button, and one production that we haven't generated yet will be generated. Now, how many productions do we still need to generate. Click on the “What's Left?” button to find out. We will see the remaining two transitions highlighted, but we will also see state “q1” highlighted. This is because any final state carries the production to λ. Feel free to click on the rest of transitions and the final state, or the “Show All” button, which will add the rest of the productions to the graph. After finishing, the following should be your list of productions (even if not exactly in that order):

When finished, click on the “Export” button, and you should have a new grammar on the screen resembling the screen below:

This concludes our brief tutorial on converting FAs into regular right-linear grammars. Thanks for reading!