Greibach-Normalform
The Greibach normal form is a term of theoretical computer science which is related to context-free languages of interest. It is named after the U.S. computer scientist Sheila A. Greibach, and describes a normal form of context-free grammars. Each context-free grammar, after the empty word can not be derived, can be transformed into a Greibach Normal Form. The outstanding feature of the Greibach normal form is that exactly one terminal symbol is needed for every derivation step. This makes it the natural intermediate step in the transformation of a context-free grammar into an equivalent non-deterministic pushdown automata without transitions.
Another normal form for context-free grammars, the Chomsky normal form.
Formal definition
Be a context-free grammar (see Chomsky hierarchy ), ie, with. This is the set of non- terminal symbols, the set of terminal symbols, the set of production rules and the start symbol. Be the empty element.
Is in Greibach Normal Form ( GNF short ) if all productions are of the form with, where a terminal symbol and is and are for non-terminals. The special feature of this form is, therefore, that on the right hand side of each production is exactly one terminal symbol followed by any number of non-terminals is. However, it is especially possible that only one terminal symbol is on the right side of the production.
With one obtains a regular grammar as a special case of a context-free grammar in Greibach normal form.
For anyone it is a, with, in Greibach normal form.
If, however, it may never happen on the right side of a production. This ensures that even languages which contain the empty word, can be generated by a grammar in Greibach normal form.
Construction of the GNF
Starting from the Chomsky normal form, there is the following algorithm for converting a grammar in the Greibach normal form. Here are below:
- Nonterminals ( represented here already existing and newly introduced in the schema nonterminal symbols)
- Consequences of nonterminals ( for example )
- Terminals and
- The set of variables.
Renaming of nonterminals
If necessary, you can rename the nonterminals occurring in having to order the below diagram reproduced correctly. For this purpose, proceed as follows:
- The first occurring nonterminal will be renamed.
- The second occurring nonterminal will be renamed.
- This pattern continues until you have replaced all existing non-terminals.
Example:
- First occurring variable is renamed.
- Second -occurring variable is renamed.
- Leads to this scheme further to get to
Onset of productions
There is a rule of the form with, it must be replaced.
Example: with a will.
This substitution, we begin with the highest i and work our way up to the 1 downstairs.
Replacing left recursive rules
Left recursive rules have the form, ie, a variable can again derive to themselves. By the previous step of the algorithm is assured, that begin with either a terminal or a.
By repeatedly inserting one easily sees that exactly the Regular left recursive rules by expression
Can be generated. This can be easily simulated: Replace the rules with:
And add new rules for a:
.
As of now there are only rules of the form
Replace the rules that begin with a non-terminal
Now we can use the productions, this non- terminals in all the rules, the first to derive a nonterminal.
As of now there are only rules of the form.
Continue until the end of
Now, the design rules are applied by analogy to all the rules of B.
A more severe variant of Greibach normal form
It is also possible to transform the productions of a context- free grammar in Greibach normal form, that occur more than 2 variables on each right-hand side. The resulting productions so then have the form, or.
Construction of a pushdown automaton from the GNF
To construct from a grammar in GNF a pushdown automaton, choose the set of states of a, the basement alphabet, the tape alphabet, the basement start symbol and the set of final states. Choose As a transition relation. accepted on empty stack. Proof by induction.