3/27/25, 11:59 PM Greibach Normal Form (GNF) | GATE Notes

Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests - Download the BYJU'S Exam Prep App fo

DOWNLOAD NOW (http://bit.ly/3i8IueA) ×

BYJU'S GATE (/gate/) > GATE (/gate/gate-exam/) > GATE Study Material (/gate/study-material/) > Greibach Normal Form (CNF) (/gate/greibach-normal-form-cnf-notes/)

(tel:+919241333666)

Greibach Normal Form (GNF)

A context-free grammar is said to be in Greibach normal form (GNF) in formal language theory if all production rules’ right-hand sides begin with
terminal symbols, optionally followed by some variables.

In this article, we will look more into the GNF according to the GATE Syllabus for (Computer Science Engineering) CSE
(https://byjus.com/gate/gate-syllabus-for-computer-science-engineering/). We will read ahead to find out more about it.

What is GNF?
The Greibach normal form is referred to as GNF. A context-free grammar (CFG) is in Greibach normal form (GNF) if and only all of its production
rules meet one of the criteria listed below:

A non-terminal that generates a terminal. For instance, X → x.

A start symbol that generates ε. For instance, S → ε.

A non-terminal that generates a terminal followed by any number of non-terminals. For instance, S → xXSY.

Example
GA = {S → xXY | xY, X → xX| x, Y → yY | y}

GB = {S → xXY | xY, X → xX | ε, Y → yY | ε}

The production rules of the GA grammar satisfy the rules that are specified for GNF; thus, the GA grammar is in GNF. But the production rule of GB
grammar does not satisfy the rules that are specified for GNF as X → ε and Y → ε contain ε (only the start symbols generate ε). Thus, the grammar
GB is not present in GNF.

CFG into GNF Conversion Steps

Step 1: Conversion of the grammar into its CNF.

In case the given grammar is not present in CNF, first convert it into CNF.

Step 2: In case the grammar exits the left recursion, eliminate it.

Step 3: If any production rule is not present in GNF, convert the production rule given in the grammar into GNF form.

Example
S → AY | XX

X → x | SX

Y→y

A→x

Answer:

https://byjus.com/gate/greibach-normal-form-cnf-notes/ 1/7
3/27/25, 11:59 PM Greibach Normal Form (GNF) | GATE Notes
As the given grammar is already in CNF, and no recursion is left, we can skip the first and the second steps and directly go to the third step.
Start your FREE GATE Preparation Today (https://ad-
With BYJU'S Exam Prep Free Trial
The production rule X → SX is not in GNF. Thus, substitute S → AY | XX in the production rule X → SX as:
Start Free Trial
S → AY | XX
tech.byjusweb.com/revive/www/delivery/cl.php?
bannerid=82&zoneid=201&sig=9bd29b5e3eed52cfbaa13a2bff86688a551920d65cfe4ac05b71169dbcf79afd&dest=https%3A%2
X → x | AYX | XXX
fta-gate-hts%3Futm_source%3Dbep_crm%26utm_medium%3Dseo_pages%26utm_campaign%3Dgate_fta)
Y→y

A→x

The production rule S → AY and Y → AYX is not in GNF. Thus, substitute A → x in the production rule S → AY and Y → AYX as:

S → xY | XX

X → x | xYX | XXX

Y→y

A→x

We will now remove left recursion (X → XXX), then get:

S → xY | XX

X → xZ | xYXZ

Z → XXZ | ε

Y→y

A→x

Removal of the null production Z → ε would get:

S → xY | XX

X → xZ | xYXZ | x | xYX

Z → XXZ | XX

Y→y

A→x

The production rule S → XX is not in GNF; thus, substitute X → xZ | xYXZ | x | xYX in production rule S → XX as:

S → xY | xZX | xYXZX | xX | xYXX

X → xZ | xYXZ | x | xYX

Z → XXZ

Z → xZX | xYXZX | xX | xYXX

Y→y

A→x

The production rule C → XXZ is not in GNF, so substitute X → xZ | xYXZ | x | xYX in production rule Z → XXZ as:

S → xY | xZX | xYXZX | xX | xYXX

X → xZ | xYXZ | x | xYX

Z → xZXZ | xYXZXZ | xXZ | xYXXZ

Z → xZX | xYXZX | xX | xYXX

Y→y

A→x

Hence, this is the GNF form for the grammar G.

https://byjus.com/gate/greibach-normal-form-cnf-notes/ 2/7
3/27/25, 11:59 PM Greibach Normal Form (GNF) | GATE Notes
Keep learning and stay tuned to get the latest updates on the GATE Exam (https://byjus.com/gate/gate-exam/) along with Eligibility Criteria, GATE
Start your FREE GATE Preparation Today (https://ad-
Syllabus for CSE (Computer Science Engineering) (https://byjus.com/gate/gate-syllabus-for-computer-science-engineering/), GATE 2023
With BYJU'S Exam Prep Free Trial
(https://byjus.com/gate/), GATE Admit Card (https://byjus.com/gate/gate-admit-card/), GATE CSE Notes (https://byjus.com/gate/gate-notes-
for-cse/), GATE CSE Question Paper (https://byjus.com/gate/gate-cse-question-paper/), and more.
tech.byjusweb.com/revive/www/delivery/cl.php?
bannerid=82&zoneid=201&sig=9bd29b5e3eed52cfbaa13a2bff86688a551920d65cfe4ac05b71169dbcf79afd&dest=https%3A%2
fta-gate-hts%3Futm_source%3Dbep_crm%26utm_medium%3Dseo_pages%26utm_campaign%3Dgate_fta)

Join BYJU'S Learning Program

Name

Mobile Number

Submit

(https://ad-tech.byjusweb.com/revive/www/delivery/cl.php?

https://byjus.com/gate/greibach-normal-form-cnf-notes/ 3/7
3/27/25, 11:59 PM Greibach Normal Form (GNF) | GATE Notes
bannerid=86&zoneid=111&OXLCA=1&sig=3db76378521bec0285a81b7e6a8da07d85217d30e75f4f11adb618a720fad2f3&dest=https%3A%2F%2Fbyjusexam
Start your FREE GATE Preparation Today
test-
(https://ad-
With BYJU'S Exam Prep Free Trial
series%3FopenLogin%3Dy%26jsdelay%3Dfalse%26utm_campaign%3DbyjusIntegration%26utm_medium%3DTSWidget%26utm_source%3DGovtExam)

tech.byjusweb.com/revive/www/delivery/cl.php?
bannerid=82&zoneid=201&sig=9bd29b5e3eed52cfbaa13a2bff86688a551920d65cfe4ac05b71169dbcf79afd&dest=https%3A%2
fta-gate-hts%3Futm_source%3Dbep_crm%26utm_medium%3Dseo_pages%26utm_campaign%3Dgate_fta)

(https://ad-tech.byjusweb.com/revive/www/delivery/cl.php?
bannerid=140&zoneid=333&OXLCA=1&sig=ccd79e0a55a8e5b9608e31c0c3dfdb360e88822b79068da642840fce9ddf9a79&dest=https%3A%2F%2Fbyju
year-
papers%3FopenLogin%3Dy%26jsdelay%3Dfalse%26utm_campaign%3DbyjusIntegration%26utm_medium%3DPYSP%26utm_source%3DGATE)

https://byjus.com/gate/greibach-normal-form-cnf-notes/ 4/7
3/27/25, 11:59 PM Greibach Normal Form (GNF) | GATE Notes

Start your FREE GATE Preparation Today (https://ad-

With BYJU'S Exam Prep Free Trial

tech.byjusweb.com/revive/www/delivery/cl.php?
bannerid=82&zoneid=201&sig=9bd29b5e3eed52cfbaa13a2bff86688a551920d65cfe4ac05b71169dbcf79afd&dest=https%3A%2
fta-gate-hts%3Futm_source%3Dbep_crm%26utm_medium%3Dseo_pages%26utm_campaign%3Dgate_fta)

(https://ad-tech.byjusweb.com/revive/www/delivery/cl.php?
bannerid=141&zoneid=334&OXLCA=1&sig=6676ae51bd547f3c7a2405450200c1681f75006eee40eeaca90ff958c23cc5a2&dest=https%3A%2F%2Fbyjusex
test%2Fgate-exams%3Futm_source%3Dbyjus.com%26utm_medium%3Dgate-sidebanner%26utm_campaign%3Dbyjus-exam-prep-
scholarship-test-2024-21-jan)

COURSES EXAMS

CBSE (/cbse/) CAT Exam (/cat/exam-info/)

ICSE (/icse/) CAT 2023 (/cat/cat-2023/)

CAT (/cat/) GATE Exam (/gate/gate-exam/)

IAS (/ias/) GATE 2024 (/gate/gate-2024/)

JEE (/jee/) IAS Exam (/ias-exam/)

NEET (/neet/) UPSC Exam (/free-ias-prep/upsc-exam/)

Commerce (/commerce/) UPSC Syllabus (/ias/upsc-syllabus/)

JEE Main (/jee/jee-main/) UPSC 2023 (/free-ias-prep/upsc-2023/)

NCERT (/ncert/) Bank Exam (/bank-exam/)

https://byjus.com/gate/greibach-normal-form-cnf-notes/ 5/7
3/27/25, 11:59 PM Greibach Normal Form (GNF) | GATE Notes
JEE Advanced (/jee-advanced/) Government Exams (/govt-exams/)
Start your FREE GATE Preparation Today (https://ad-
UPSC Prelims 2022 Question Paper (/free-ias-prep/upsc-prelims-2022-question-papers-pdf/) Education News (/news/)
With BYJU'S Exam Prep Free Trial
UPSC Prelims 2022 Answer Key (/free-ias-prep/upsc-prelims-answer-key-2022/)
CLASSES
IAS Coaching (/ias-coaching/)
tech.byjusweb.com/revive/www/delivery/cl.php?
CBSE Sample Papers (/cbse/cbse-sample-papers/) Kids Learning (/kids-learning/)
bannerid=82&zoneid=201&sig=9bd29b5e3eed52cfbaa13a2bff86688a551920d65cfe4ac05b71169dbcf79afd&dest=https%3A%2
Class 1st - 3rd (/disney-byjus-early-learn/)
CBSE Question Papers (/cbse-study-material/cbse-previous-year-question-paper/)
fta-gate-hts%3Futm_source%3Dbep_crm%26utm_medium%3Dseo_pages%26utm_campaign%3Dgate_fta)
Class 4th - 5th (/class-4-5/)

Class 6th - 10th (/class-6-10/)

Class 11th - 12th (/class-11-12/)

BYJU'S Tuition Centre (/btc/)

EXAM PREPARATION COMPANY

Free CAT Prep (/free-cat-prep/) About Us (/about-us/)

Free IAS Prep (/free-ias-prep/) Contact Us (/contact-us/)

Maths (/maths/) Contact our Financial Partners (https://byjus.com/our-financial-

partners/)
Physics (/physics/)
Investors (/our-investors/)
Chemistry (/chemistry/)
Compliance (/compliance/)
Biology (/biology/)
Careers (/careers-at-byjus/)
JEE 2024 (/jee/jee-2024/)
CIRP (/cirp/)
JEE Advanced 2023 Question Paper with Answers (/jee/jee-advanced-2023-question-paper/)
BYJU'S in Media (/press/)
JEE Main Mock Test (/jee/jee-main-mock-test/)
Social Initiative - Education for All (/educationforall/)
JEE Main 2024 Question Papers with Answers (/jee/jee-main-2024-question-papers/)
BYJU'S APP (/byjus-the-learning-app/)
JEE Main 2023 Question Papers with Answers (/jee/jee-main-2023-question-papers/)
FAQ (/faq/)
JEE Advanced 2022 Question Paper with Answers (/jee/jee-advanced-2022-question-paper/)
Support (/customer-care/)
NEET 2023 Question Paper (/neet/neet-2023-question-paper/)
Students Stories - The Learning Tree (https://blog.byjus.com/the-
NEET 2023 Question Paper Analysis (/neet/neet-2023-question-paper-analysis/)
learning-tree/)
NEET 2022 Answer Key (/neet/neet-2022-answer-key/)
Faces of BYJU'S – Life at BYJU'S (https://blog.byjus.com/life-at-
BYJU'S Exam Prep (https://byjusexamprep.com/) byjus/)

Blog (https://blog.byjus.com/)
RESOURCES BYJU'S Give (/give/)

CAT College Predictor (/free-cat-prep/cat-college-predictor/)

Worksheets (/worksheets/)

BYJU'S Answer (/question-answer/)

DSSL (/about-dssl/)

Home Tuition (/home-tuition/)

All Products (https://shop.byjus.com)

Calculators (/calculators/)

Formulas (/formulas/)

FREE TEXTBOOK SOLUTIONS STATE BOARDS

(/textbook-solutions/) Maharashtra (/msbshse/)

NCERT Solutions (/ncert-solutions/)
Gujarat (/gseb/)
NCERT Exemplar (/ncert-exemplar/)
Tamil Nadu (/tn-board/)
NCERT Solutions for Class 6 (/ncert-solutions-class-6/)
Karnataka (/kseeb/)
NCERT Solutions for Class 7 (/ncert-solutions-class-7/)
Kerala (/kbpe/)
NCERT Solutions for Class 8 (/ncert-solutions-class-8/)
Andhra Pradesh (/ap-board/)
NCERT Solutions for Class 9 (/ncert-solutions-class-9/)
Telangana (/telangana-board/)
NCERT Solutions for Class 10 (/ncert-solutions-class-10/)
Uttar Pradesh (/upmsp/)
NCERT Solutions for Class 11 (/ncert-solutions-class-11/)
Bihar (/bihar-board/)
NCERT Solutions for Class 11 English (/ncert-solutions-class-11-english/)
Rajasthan (/rajasthan-board/)
NCERT Solutions for Class 12 English (/ncert-solutions-class-12-english/)
Madhya Pradesh (/mp-board/)
NCERT Solutions for Class 12 (/ncert-solutions-class-12/)
West Bengal (/west-bengal-board/)
RD Sharma Solutions (/rd-sharma-solutions/)

RD Sharma Class 10 Solutions (/rd-sharma-class-10-solutions/)

ICSE Selina Solutions (/icse/selina-solutions/)

FOLLOW US

(https://www.facebook.com/byjuslearningapp/) (https://in.linkedin.com/company/byjus)

https://byjus.com/gate/greibach-normal-form-cnf-notes/ 6/7
3/27/25, 11:59 PM Greibach Normal Form (GNF) | GATE Notes

Start your FREE GATE Preparation Today

Disclaimer (/disclaimer/) Privacy Policy (/tnc_app/#privacydesc) Terms of Services (/tnc_app/#tncdesc)
(https://ad-
Sitemap (/sitemap.xml)
With BYJU'S Exam Prep Free Trial
© 2025, BYJU'S. All rights reserved.

tech.byjusweb.com/revive/www/delivery/cl.php?
bannerid=82&zoneid=201&sig=9bd29b5e3eed52cfbaa13a2bff86688a551920d65cfe4ac05b71169dbcf79afd&dest=https%3A%2
fta-gate-hts%3Futm_source%3Dbep_crm%26utm_medium%3Dseo_pages%26utm_campaign%3Dgate_fta)

https://byjus.com/gate/greibach-normal-form-cnf-notes/ 7/7