L9 Greibach Normal Form

Greibach Normal Form
Definition Greibach Normal Form (GNF)
A CFG is in Greibach Normal Form if all productions are of the form
A ? a X
with a?T and X?V*.
This means, all productions start with a terminal on the PRODUCTION and have only variables following.
Theorem:
For every CFG G with ??L(G) exists an equivalent grammar G in Greibach NF.
Proof and algorithm
Firstly, we convert the given grammar into Chomsky NF:
Start with a grammar G = ( V, T, P, S)
Eliminate useless variables that cannot become terminals.
Eliminate useless variables that cannot be reached.
Eliminate ?-productions.
Eliminate unit productions.
Convert grammar to Chomsky Normal Form.
Then, we convert this grammar into an equivalent grammar in Greibach NF.


Convert a CNF grammar into Greibach Normal Form:
1. Re-label all variables such that the names are A1, A2, ... , Am.
2. We want to order the productions, which are not terminal but contain variables. We use for this purpose the indexing of the variables, so that
Ai ? Aj ? with i<j for all i = 1,...,m and j = 2, ..., m
We perform the ordering process by substitution of the first variable on the PRODUCTION, if the production violates the condition above (see 2 and 3).
3. We start the ordering with A1.
A1-productions can have only a higher numbered variable as first variable on the PRODUCTION, or a single terminal.
4. We assume now that all rules are okay up to Ak-1. The next rule we encounter, with Ak on the production, is the first one, which is not okay:
Ak ? Al ? with k>l
We resolve this problem by substituting Al. Since l<k, the Al-rules have already gone through the sorting process and are in the proper format: