What is Greibach's normal form?

Overview

We use normal forms in advanced topics of computation theory. Greibach's normal form and Chomsky's normal form are two methods of simplifying context-free grammar.

Greibach's normal form (GNF)

Grammar is in GNF if all the productions follow either of the following set of rules:

• A nonterminal produces a terminal.
• A nonterminal produces a terminal with a string of nonterminal symbols.

Steps to convert grammar to GNF

The following steps convert context-free grammar into Greibach's normal form.

1. Convert CFG to CNF.
2. Remove all the indirect and direct left recursions that occur in the productions, if they exist.
3. Convert all production rules into the GNF form. This is usually done by changing the names of the nonterminal symbols into $A_i$ form, in ascending order of $i$.

Recursion may also occur after step 3; regardless, it must be removed.

Note: To learn more about CNF, visit here.

Example

Let's consider the following grammar:

• This grammar is already in CNF.
• After converting the nonterminals in the $A_i$ form, grammar becomes:

We'll appoint the values in order of the occurrence of the nonterminals. In this grammar $S \equiv A_1$, $B \equiv A_2$, $A \equiv A_3$, and $T \equiv A_4$.

• We'll adjust the rules so that the nonterminals are now in ascending order. This is done when the production is in the form of $A_i \rightarrow A_j x$, where $x$ is a terminal or a nonterminal and $i<j$ and should not be $i \ge j$.
• The first production follows this property as $A_1 < A_2$ and $A_1 < A_4$.

• In the second production $A_4 > A_1$. We will replace $A_1$ with the rules it produces.

• We'll check again if $A_4 > A_2$ in the new step. Since $i \ge j$, we will replace the rules produced by $A_2$.

  The production $A_4 \rightarrow bA_3A_4$ is valid in GNF.

• Now we check again if $A_4 \ge A_4$. Again $i \ge j$ as well as an occurrence of left recursion since $A_4 \rightarrow A_4 x$. We'll now remove the left recursion from this production.

  The grammar now becomes:

Note: To learn how to remove left recursion, visit here.

• Now the entire grammar looks like this:

• Now we know that in GNF, we need to have a terminal at the beginning of a rule, not a nonterminal, and a nonterminal exists only after a terminal. So we replace $A_2$, and $A_4$ by the rules, they produce for the first production, i.e., $A_1$.

• Now, $A_1$ and $A_4$ are in GNF. We'll now convert $R$ to GNF.

Now we have finally converted a CFG to GNF.

In conclusion,

Every grammar in GNF is context-free, and every CFG can be converted into GNF.