# Automaton to Grammar Converters

Incomplete conversion of an FA to a grammar

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 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 Sq0Zq3.

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 qiAqja

- Transitions of the form a, A; BC from state qi to state qj are converted to the set of rules:
  { qiAqx a (qjBqy) (qyCqx) | qx and qy are states in the automaton}.

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