Grammar Conversion

NOTE: In grammar conversions it is best to use the lower case letters for the input alphabet and upper case letters for the stack alphabet.

Grammar conversion can be carried out from either a FSA or a PDA. Converting from a FSA to a grammar results in a regular grammar. Converting from a PDA to a grammar results in a context free grammar. When the Convert to Grammar menu option is chosen, a dialog box appears displaying a step-by-step conversion of each transition in the automaton into a set of rules in the resulting grammar. Below is an example of this dialog:

The Conversion to Grammar dialog box contains two commands:

- Next - shows the grammar rules generated for the next transition.
- Show - shows the resulting complete grammar and skips directly to the Grammar Input Window.

For each set of rules displayed in the Conversion to Grammar dialog box, a corresponding transition (if applicable) is highlighted in the window containing the automaton. Furthermore, the variables of the generated rules are colored blue while the terminals are colored red. After all of the rules have been stepped through or the Show button is pressed, the Grammar Input Window is shown with the complete grammar for the automaton.

FSA to Regular Grammar
To start off with, the FSA to Regular Grammar conversion warns the user that the labels on the states will be replaced.

If you are not user-defined labeling of the states, then press Continue. If you are using user-defined labeling and wish to preserve the names on the labels then press Cancel and save the automaton.

The actual conversion algorithm for converting from a FSA to a Regular Grammar is fairly simple. For each transition, a grammar rule is created which maps the symbol associated with the state that the transition is going from to the symbol associated with the state that the transition is going to. For example:

| would become the rule: q0 -> a q1

In addition, final states are treated differently. If a transition leads to a final state, then an additional rule is added to the grammar which maps the symbol associated with the final state to a lambda transition. For example:

| would become the rule: q2 -> lambda

PDA to Context-Free Grammar
The conversion from PDA to Context-Free Grammar requires that the PDA have a certain form before the conversion begins. The following are the requirements for this conversion:

- only one final state

- accepts if stack is empty

- each move increases or decreases the stack content by a single symbol

- each transition has the form: "a,A;" or "a,A;BC"

The last requirement is the most restrictive. An algorithm is provided to convert any transition into the form required for the PDA to Context-Free Grammar.

To convert a transition that pops one item off of the stack and places several items back onto the stack, the items that are pushed onto the stack should be split up among several transitions. For example, to convert a transition which accepts an "a", pops "A" off the stack, and pushes "BBCD" onto the stack, the following transformation would be necessary:

Similarly, any transition that pops one item from the stack and pushes one item onto the stack can be dealt with by adding a new transition. For example, to convert a transition which accepts an "a", pops "A" off the stack, and pushes "B" onto the stack, the following transformation would be necessary.

Once all of the transitions have been converted into the proper form and the rest of the requirements have been met, the conversion process can proceed normally.

NOTE: In the PDA transformation, all variables in the resulting Context Free Grammar (CFG) will be formed from two states and a symbol from the alphabet. In other words, one variable is represented in the form "qiAqj" where i and j are numbers corresponding to states in the PDA and A is a symbol in the alphabet of the PDA.

The actual rule generating begins with the starting rule. The variable for the starting rule is found by concatenating the initial state with the end of stack character("Z") and the beginning state.
For example, if an automata had an initial state q0 and a final state q3, the starting rule would be
S -> q0Zq3.

Once the starting state is established, the transitions must be processed.

- Transitions of the form "a, A; " from state qi to state qj are converted to:
  qiAqj -> a.

- Transitions of the form "a, A; BC" from state qi to state qj are converted to the set of rules
  qiAqx -> a qjBqy qyCqx such that qx and qy are states in the automaton.

Below is an example of the conversion from FSA to grammar:

- an FSA

- the equivalent regular grammar