1.
Introduction
1.1.
For example:
2.
Steps for Converting CFG into GNF
2.1.
Letâ€™s understand with an example,
3.
3.1.
How is GNF different from CNF?
3.2.
Why is GNF important?
3.3.
What is the use of Greibach Normal Form?
3.4.
Why is Greibach Normal Form used?
4.
Conclusion
Last Updated: May 6, 2024
Medium

# Greibach Normal Form (GNF)

GAZAL ARORA
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

GNF (Greibach Normal Form) is a specialized form of Context-Free Grammar (CFG) where each production rule begins with a terminal symbol, followed by optional variables.

A CFG (Context-Free Grammar) is a Greibach Normal Form(GNF) if all of its production rules satisfy one of the following conditions:

1. A non-terminal generating terminal. For example,  B -> b.
2. Start symbol generating Îµ. For example, S â†’ Îµ.
3. A non-terminal generates a terminal followed by any number of non-terminals. For example, A -> aBCâ€¦N.

### For example:

``````G1 = {S â†’ aAB | bBA, A â†’ aA | a, B â†’ bB | b}
G2 = {S â†’ aAB | aBA, A â†’ aA | Îµ, B â†’ bB | Îµ}  ``````

• The production rules of Grammar G1 satisfy the above rules specified for GNF. Therefore, G1 is in GNF.
• However, the production rule of G2 does not satisfy the rules specified for GNF as A â†’ Îµ and B â†’ Îµ contains Îµ, but only the start symbol can generate Îµ. So the grammar G2 is not in GNF.

Notes:

1. There can be more than one GNF for a given grammar.
2. GNF produces the same language as CFG produces.

Also see, Turing Machine in TOC.

## Steps for Converting CFG into GNF

Step 1 - Convert the Grammar into Chomsky Normal Form(CNF): If the given Grammar is not in CNF, convert it.

Step 2 - If the grammar contains left recursion, remove it.

Step 3 - Convert the production rule into GNF form in the grammar.

### Letâ€™s understand with an example,

Question: Consider the following Grammar G. Convert it into GNF.

``````S â†’ AA | BC
A â†’ a|SA
B â†’ a
C â†’ c``````

Solution:

We can skip steps 1 and 2 and move directly to step 3 because the given grammar G is already in CNF, and there is no left recursion.

1. The production rule A â†’ SA is not in GNF, so we substitute S -> AA | BC in the production rule A â†’ SA as
``````S â†’ AA | BC
A â†’ a | AAA | BCA
B â†’ a
C â†’ c``````

2. The production rule S â†’ BC and A â†’ BCA is not in GNF, so we substitute B â†’ a in the production rule S â†’ BC and A â†’ BCA as

``````S â†’ AA | aC
A â†’ a | AAA | aCA
B â†’ a
C â†’ c``````

3. Next, we will remove the left recursion (A â†’ AAA), we get

``````S â†’ AA | aC
A â†’ aX | aCAX
X â†’ AAX | Îµ
B â†’ a
C â†’ c``````

4. Now remove the null production X â†’ Îµ, we get

``````S â†’ AA | aC
A â†’ aX | aCAX | a | aCA
X â†’ AAX | AA
B â†’ a
C â†’ c``````

5. Now, S â†’ AA  and X â†’ AA are not in GNF, so we substitute A â†’ aX | aCAX | a | aCA in production rule S â†’ AA and X â†’ AA as

``````S â†’ aXA | aCAXA | aA | aCAA | aC
A â†’ aX | aCAX | a | aCA
X â†’ AAX
X â†’ aXA | aCAXA | aA | aCAA
B â†’ a
C â†’ c``````

6. Lastly, X â†’ AAX is not in GNF,  so we substitute A â†’ aX | aCAX | a | aCA in production rule X â†’ AAX as

``````S â†’ aXA | aCAXA | aA | aCAA | aC
A â†’ aX | aCAX | a | aCA
X â†’ aXAX | aCAXAX | aAX | aCAAX
X â†’ aXA | aCAXA | aA | aCAA
B â†’ a
C â†’ c``````

Hence, it is the GNF of Grammar G, as all the production rules follow one of the rules mentioned above.

Also read - Theory of Computation

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### How is GNF different from CNF?

CNF and GNF are two normal forms used in formal language theory to simplify context-free grammar. CNF stands for Chomsky Normal Form, named after the mathematician Noam Chomsky. GNF stands for Greibach Normal Form, named after the mathematician Sheila Greibach.

### Why is GNF important?

GNF, or Greibach Normal Form, is crucial in parsing theory and compiler design. It simplifies grammars, aids in understanding, and facilitates efficient parsing algorithms like CYK.

### What is the use of Greibach Normal Form?

In contrast to the Chomsky Normal Form, each and every derivation of a production rule will result in one terminal along with optional non-terminals. Hence it tells what the first terminal symbol to be derived using a production rule is. It is very much used in formal language theory.

### Why is Greibach Normal Form used?

Greibach Normal Form (GNF) is a normal form for context-free grammar, which has several important uses in the study of formal languages and automata. It can be used for parsing algorithms, language recognition, complexity analysis, and compiler design.

## Conclusion

In this article, we learned about GNF. GNF stands for Greibach Normal Form. We also learned about the algorithm to convert the normal form of a Grammar into Greibach Normal Form.