Scribd
Upload
349 views3 pages

CFG To GNF

The document explains how to convert a Context Free Grammar (CFG) into Greibach Normal Form (GNF), detailing the criteria for GNF and providing examples. It outlines a step-by-step process that includes converting to Chomsky Normal Form (CNF), eliminating left recursion, and ensuring production rules conform to GNF. Two cases are presented to illustrate grammars that either meet or do not meet GNF criteria.

Uploaded by

juhi.nljiet
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
349 views3 pages

CFG To GNF

The document explains how to convert a Context Free Grammar (CFG) into Greibach Normal Form (GNF), detailing the criteria for GNF and providing examples. It outlines a step-by-step process that includes converting to Chomsky Normal Form (CNF), eliminating left recursion, and ensuring production rules conform to GNF. Two cases are presented to illustrate grammars that either meet or do not meet GNF criteria.

Uploaded by

juhi.nljiet
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

3/27/25, 11:33 PM How to convert CFG to Greibach Normal Form?

How to convert CFG to Greibach Normal Form?


Data Structure Algorithms Computer Science Computers

A Context Free Grammar (CFG) is said to be in Greibach Normal Form(GNF), if


production rules satisfy one of the following criteria −

Only a start symbol can generate ε. For example, if S is the start symbol then
S → ε is in GNF.

A non-terminal can generate a terminal. For example, if A is Non terminal


and a is terminal then, A → a is in GNF.

A non-terminal can generate a terminal followed by any number of non-


terminals. For Example, S → aAS is in GNF.

Case 1
G1 = {S → aAB | aB, A → aA| a, B → bB | b}

The production rules of G1 satisfy the rules specified for GNF, then the grammar G1 is in
GNF.

Case 2
G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}

The production rule of G2 is not satisfying the rules specified for GNF as

A → ε and B → ε contain ε(only the start symbol can generate ε).

So, the grammar G2 is not in GNF.

Explore our latest online courses and learn new skills at your own pace. Enroll and
become a certified expert to boost your career.

Steps for converting CFG into GNF

https://www.tutorialspoint.com/how-to-convert-cfg-to-greibach-normal-form 1/3
3/27/25, 11:33 PM How to convert CFG to Greibach Normal Form?

Step 1 − Convert the grammar into CNF. If the given grammar is not in CNF,
convert it into CNF.

Step 2 − If the grammar consists of left recursion, eliminate it. If the context
free grammar contains any left recursion, eliminate it.

Step 3 − In the grammar, convert the given production rule into GNF form.
If any production rule in the grammar is not in GNF form, convert it.

Example

Consider the context free grammar

S→SS|(S)|a

Convert this grammar to Greibach Normal Form.

Solution

Given below is an explanation for conversion of CFG to GNF −

Step 1:
Converting to CNF:
S->SS|XSY|a
X->(
Y->)

Step 2:
Remove left recursion from S->SS
S->XSYP/aP
P->SP/ε
X->(
Y->)

Step 3:
Remove null production P->ε
S->XSYP/aP
P->SP/S
X->(
Y->)

Step 4:
Convert to GNF as S->XSYP is not in GNF,
Replace X with (
S->(SYP/aP
P->SP/S

https://www.tutorialspoint.com/how-to-convert-cfg-to-greibach-normal-form 2/3
3/27/25, 11:33 PM How to convert CFG to Greibach Normal Form?

X->(
Y->)

Step 5:
Convert to GNF as P->SP is not in GNF,
Replace S with (SYP/aP
S->(SYP/aP
P->(SYPP/aPP/(SYP/aP
X->(
Y->)

https://www.tutorialspoint.com/how-to-convert-cfg-to-greibach-normal-form 3/3

You might also like