Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
For example:
2.
Steps for Converting CFG into GNF
2.1.
Let’s understand with an example,
3.
Frequently Asked Questions
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)

Author 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.
Greibach Normal Form(GNF)

Also read about - Chomsky Hierarchy

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.

Also read,  Arden's theorem

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. 

Read About - Simplification of CFG

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

Frequently Asked Questions

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.

Recommended Readings:


Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

Also check out the Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Previous article
Chomsky Normal Forms(CNF)
Next article
Pumping Lemma for Context Free Language(CFL)
Live masterclass