Automaton to Grammar Converters

To add the productions for an object, click on an object that corresponds to a production in the FA. If a grammar production is selected, the object in the automaton that it was generated by will be highlighted. Eventually all productions will be added, and the grammar may be exported. For an FA, there will be exactly one production for every transition and final state. For a PDA, there will be productions for only transitions, though there may be many of them. Specialized notes for these two operations are written below.

The tool bar has some helpful controls:

Hint

This will convert one object (transition or, in the case of FA, final state) to the appropriate set of productions.

Show All

All remaining productions will be added.

What's Left?

All convertible but as yet unconverted objects will be highlighted.

Export

Once conversion has finished, the grammar may be output.

FA to Grammar

This operation converts a FA to a regular (specifically right linear) grammar. This operation is featured in the window above. Each state in the FA corresponds to a variable in the grammar, which is shown slung beneath each state. The terminals for the grammar are the symbols on the transitions.

Each transition and each final state correspond to a production in the grammar, with finals states correspond to lambda productions, and for a transition of a between two states labeled A to B, the production A aB is added.

PDA to Grammar

The conversion from PDA to Context-Free Grammar requires that the PDA have a certain form before the conversion begins:

• only one final state

• accepts only if stack is empty

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

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 q_iAq_j 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 q₀ and a final state q₃, the starting rule would be Sq₀Zq₃.

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

• Transitions of the form a, A; from state q_i to state q_j are converted to q_iAq_ja

• Transitions of the form a, A; BC from state q_i to state q_j are converted to the set of rules:
  { q_iAq_x a (q_jBq_y) (q_yCq_x) | q_x and q_y are states in the automaton}.

When exporting, each of the q_iAq_j symbols has a single character variable substituted in its place.