greibach normal form

Greibach Normal Form (GNF):
A CFG G = (V, T,R, S) is said to be in GNF if every production is of the form A ? a?, where a ? T and ?? V *, i.e., ? is a string of zero or more variables. For every CFG G with ??L(G) exists an equivalent grammar G in Greibach NF.
Convert a CNF grammar into Greibach Normal Form:
Re-label all variables such that the names are A1, A2, ... , Am.
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 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.
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 lAl ? Aj ? with lNow, we substitute the productions of Al in the Ak-rule, and come up with:
Ak ? Al ? or Ak ? a for some a
If l is still less than k, we substitute again. And again and again, until we get at least Ak on the production - all rules up to Ak-1 are already sorted and in proper form, and the first variable on the PRODUCTION of the Ak-1-production must be therefore at least Ak.