23CS(AI&DS)7301

AUTOMATA AND COMPILER DESIGN

UNIT - 2
Context Free grammars and parsing: Context free grammars, derivations, parse trees,
ambiguity, simplification of CFG, Normal Forms: CNF and GNF.
Top Down and Bottom up Parsing: LL(K) grammars and LL(1) parsing, Bot-tom up parsing,
handle pruning, LR Parsing, parsing using ambiguous grammars. Computing FIRST and
FOLLOW terms (LTC)

Grammar
The set of production rules which are used for generate the strings is call as
Grammar. In Theory of Computation, grammar refers to a formal system that defines how
strings in a language are constructed. It plays a crucial role in determining the syntactic
correctness of languages and forms the foundation for parsing and interpreting programming
languages, natural languages, and other formal systems.

Grammar in Computation
Grammar is a formal system that defines a set of rules for generating valid strings within
a language. It serves as a blueprint for constructing syntactically correct sentences or
meaningful sequences in a formal language.
Grammar is basically composed of two basic elements:
 Terminal Symbols: Terminal symbols are those that are the components of the sentences
generated using grammar and are represented using small case letters like a, b, c, etc.
 Non-Terminal Symbols: Non-terminal symbols are those symbols that take part in the
generation of the sentence but are not the component of the sentence. Non-Terminal
Symbols are also called Auxiliary Symbols and Variables. These symbols are represented
using a capital letters like A, B, C, etc.

Representation of Grammar
Any Grammar can be represented by 4 tuples - <V, T, P, S>
 V - Finite Non-Empty Set of Non-Terminal Symbols.
 T - Finite Set of Terminal Symbols.
 P - Finite Non-Empty Set of Production Rules.
 S - Start Symbol (Symbol from where we start producing our sentences or strings).

Production Rules
A production or production rule in computer science is a rewrite rule specifying a symbol
substitution that can be recursively performed to generate new symbol sequences. It is of the
form α-> β where α is a Non-Terminal Symbol which can be replaced by β which is a string
of Terminal Symbols or Non-Terminal Symbols.
Example 1
Consider Grammar G1 = <V, T, P, S>
T = {a,b} #Set of terminal symbols
 1 2 3 4 5
P = { A -> Aa, A -> Ab, A -> a ,A -> b, A -> 𝜺} #Set of all production rules
S = {A} #Start Symbol
As the start symbol S is equivalent to A then we can produce Aa, Ab, a, b, 𝜺 strings. These
strings can further produce strings where A can be replaced by the strings mentioned in the
production rules. Hence this grammar can be used to produce strings of the form (a+b)*.

Derivation of Strings
A->a #using production rule 3
OR
A->Aa #using production rule 1
Aa->ba #using production rule 4
OR
A->Aa #using production rule 1
Aa->AAa #using production rule 1
AAa->bAa #using production rule 4
bAa->ba #using production rule 5
Example 2

Consider Grammar G2 = <V, T, P, S>

N = {A} #Set of non-terminals Symbols
T = {a} #Set of terminal symbols
1 2 3 4
P = {A -> Aa, A -> AAa, A -> a, A -> 𝜀} #Set of all production rules
S = {A} #Start Symbol
As the start symbol is S then we can produce Aa, AAa, a, which can further produce strings
where A can be replaced by the Strings mentioned in the production rules and hence this
grammar can be used to produce strings of form (a)*.
Derivation of Strings
A->a #using production rule 3
OR
A->Aa #using production rule 1
Aa->aa #using production rule 3
OR
A->Aa #using production rule 1
Aa->AAa #using production rule 1
AAa->Aa #using production rule 4
Aa->aa #using production rule 3

Equivalent Grammars
Two grammars are said to be equivalent if they generate the same language. For instance, if
Grammar 1 and Grammar 2 both generate strings of the form (𝑎+𝑏)∗, they are considered
equivalent.

Types of Grammars
There are several types of Grammar. We classify them on the basis mentioned below.
 Type of Production Rules: The form and complexity of the production rules define the
grammar type, such as context-free, context-sensitive, regular, or unrestricted grammars.
 Number of Derivation Trees: The number of ways a string can be derived from the
grammar. Ambiguous grammars have multiple derivation trees for the same string.
 Number of Strings: The size and nature of the language generated by the grammar.

Chomsky Hierarchy of Languages:

Chomsky classified the grammars into four types in terms of productions
(types 0-3) which is as shown in the table below:

Type 0 Grammar or Unrestricted Turing Machines

Grammar

Type 1 Grammar or Context Linear Bounded Automata

Sensitive Grammar
Type 2 Grammar or Context Push Down Automata
Free Grammar
Type 3 Grammar or Finite Automata
Regular Grammar

Grammar Languages Automaton Production Rules

Recursively enumerable/ Turing machines αβ
Type 0
Phrase Structured
Linear Bounded αβ
Type 1 Context Sensitive Language
Automata | α |<=| β |
Type 2 Context Free Languages Push Down Automata Aα
 Aw
Type 3 Regular Languages Finite Automata AwB
ABw

Type 0 Grammar:-
This grammar is also called as phase structured grammar. In this grammar the
Right Hand Side of production are free from any restriction. This is also called as
unrestricted grammar. The language generated by Type 0 grammar is Recursively
Enumerable Language.

Type 1 Grammar:-
It is also called as context sensitive grammar. the production should be of the p form αβ
Such that |α|≤|β| the grammar which contains all type 1 productions such grammar is
called Type 1 grammar or context sensitive grammar.
Language generated by the context sensitive grammar (CSG) is called Context Sensitive
Language(CSL).
Example:-
1. S-->aS,
S-->AB,
S-->Aab

2. AS-->a (not valid)

Type 2 Grammar:-
A production of the form αβ , such that β ∈ (V U T)*. Then it is called Type 2
production. If a grammar contains all type 2 productions. That is called as type 2
grammar. This is also called as Context Free Grammar. The language generated by the
Context Free Grammar is called as Context Free Language(CFL)
Example:
S-->aA
S-->BAD

Type 3 Grammar:-
Type-3 grammars (regular grammars) generate the regular languages. Such a grammar
restricts its rule to a single non-terminal on the left-hand side and a right-hand side
consisting of a single terminal, possibly followed or precedes, but not both in the same
grammar by a single non- terminal. A production S→ε is allowed in Type-3 grammar, but
in this case S does not appear on the right hand side of any production.
Example:-
S-->a,
S-->b,
S-->aA,
A-->a
Regular Grammar:
A regular grammar is a formal grammar that describes the regular language.
Where a formal grammar is defined as a set of rules for rewriting the strings, along with
a start symbol from which the rewriting must start.

The regular grammars are of two types:

1) left linear grammars and
2) right linear grammars.

Right Linear Regular Grammar

In this type of regular grammar, all the non-terminals on the right-hand side exist at
the rightmost place, or at the right ends.
Examples :
A ⇢ a, A ⇢ aB, A ⇢ ∈
where,
A and B are non-terminals,
a is terminal, and
∈ is empty string

S ⇢ 00B | 11S
B ⇢ 0B | 1B | 0 | 1
where,
S and B are non-terminals, and
0 and 1 are terminals

Left Linear Regular Grammar

In this type of regular grammar, all the non-terminals on the left-hand side exist at
the leftmost place, or at the left ends.
Examples :
A ⇢ a, A ⇢ Ba, A ⇢ ∈
where,
A and B are non-terminals,
a is terminal, and
∈ is empty string

S ⇢ B00 | S11
B ⇢ B0 | B1 | 0 | 1
where
S and B are non-terminals, and
0 and 1 are terminals
Context Free Grammar:
A context-free grammar (CFG) is a formal system used to describe a class of languages
known as context-free languages (CFLs). Purpose of context-free grammar is:
 To list all strings in a language using a set of rules (production rules).
 It extends the capabilities of regular expressions and finite automata.
A CFG (or just a grammar) G is a tuple G = (V, T, P, S) where
 V is the (finite) set of variables (or non terminals or syntactic categories). Each variable
represents a language, i.e., a set of strings
 T is a finite set of terminals, i.e., the symbols that form the strings of the language being
defined
 P is a set of production rules that represent the recursive definition of the language.
 S is the start symbol that represents the language being defined. Other variables represent
auxiliary classes of strings that are used to define the language of the start symbol.

A grammar is said to be the Context-free grammar if every production is in the form of:
G -> (V∪T)* , where G ∊ V
 V (Variables/Non-terminals): These are symbols that can be replaced using production
rules. They help in defining the structure of the grammar. Typically, non-terminals are
represented by uppercase letters (e.g., S, A, B).
 T (Terminals): These are symbols that appear in the final strings of the language and
cannot be replaced further. They are usually represented by lowercase letters (e.g., a, b,
c) or specific symbols.
 The left-hand side can only be a Variable, it cannot be a terminal.
 But on the right-hand side here it can be a Variable or Terminal or both combination of
Variable and Terminal.

The above equation states that every production which contains any combination of the
'V' variable or 'T' terminal is said to be a context-free grammar.

Core Concepts of CFGs

A CFG is defined by:
 Nonterminal symbols (variables): Represent abstract categories or placeholders
(e.g., E,SE,S).
 Terminal symbols (alphabet): The actual characters or tokens in the language
(e.g., a, b,+,∗,(,)a, b, +, *, (, )a, b,+,∗,(,)).
 Production rules: Specify how non terminals can be replaced with other non terminals
or terminals
(e.g., E→E+EE → E + EE→E+E).
 Start symbol: A special nonterminal from which derivations begin.

 Find the language generated by the given grammar.

SSS
Sa
Sol: V= set of variables={S}
T=set of terminals={a}
P=set of productions={SSS/a}
 S= start symbol=S .

S⟹aS
S⟹aSS
S⟹aSSS
S⟹aaSS
S⟹aaSSS
S⟹aaaSS
S⟹aaaaS
S⟹aaaaa
Language generated by G is L(G)= { ai | i>=2}.
In the given productions we have production in the form of Sa . So we have single
a ϵ L(G).
hence the language generated by given language G id L(G)={ai | i>=1}.

 Find the language generated by the given grammar.

SSS
Saa
S ϵ
Sol: V= set of variables={S}
T=set of terminals={a}
P=set of productions={SSS/aa/ ϵ }
S= start symbol=S .
S⟹SS
S⟹SSS
S⟹aaSS
S⟹aaSSS
S⟹aaaaSS
.
.
.
.
S⟹ (aa)n
∴ L(G)={(aa)n|n>=1} or {a2n | n>=1}
But we have production S ϵ. Such that ε ϵ L(G).So the language generated by
given grammar G is L(G)= { a2n|n>=0} or {(aa)n |>=0}.

 Generate grammar for the language L= {bnan/n>=0}

Strings generated by the given language
L={ ϵ, ba, bbaa, bbbaaa……}
We have ϵ in the string. So we have production as S ϵ
Then by observing set of strings generated by language. Equal number of b’s
followed by equal number of a’s.
So we have productions like SbS
Sba
The required grammar generated by the given language is SbSa|ba| ϵ.
 Tuple representation:
------------------------------
G(V,T,P,S)
V={S}
T={b,a}
P={ SbSa|ba| ϵ}
SS.

 Find the grammar for the language L= {anb2n|n>=1}

L= {anb2n|n>=1}
Strings generated by the given language
L={ ϵ,abb,aabbbb,aaabbbbbb……}
When n=1, abb
N=2, aabbbb.
Language generates the strings in the form above so that produces
grammar like following productions.
S⟹abb
S⟹aSbb.

Tuple representation:
------------------------------
G(V,T,P,S)
V={S}
T={b,a}
P={ Sabb|aSbb}
SS.
 Find the grammar for the language L= {an cm dm bn | n, m >=1}
Strings generated by the given language
L={ acdb, accddb, aacdbb, aaaccddbbb……}

So The required grammar have fillowing productions.

S⟹aSb
S⟹aAb
S⟹cAd
S⟹cd
Tuple representation:
------------------------------
G(V,T,P,S)
V={S}
T={b,a}
P={ SaSb|aAb|,AcAd|cd}
SS.

Derivation

Derivation is a sequence of production rules. It is used to get the input string through
these production
rules.

During parsing, we have to take two decisions. These are as follows:

o We have to decide the non-terminal which is to be replaced.
o We have to decide the production rule by which the non-terminal will be replaced.

We have two options to decide which non-terminal to be placed with production rule.

1. Leftmost Derivation:
In the leftmost derivation, the input is scanned and replaced with the production rule
from left to right.
So in leftmost derivation, we read the input string from left to right.

Example:
Consider the grammar SS+S, SS*S, Sa, Sb.

Derive the string w=a*a+b.

S⟹S*S
S⟹a*S
S⟹a*S+S
S⟹a*a+S
S⟹a*a+b

2. Rightmost Derivation:
In rightmost derivation, the input is scanned and replaced with the production rule
from right to left.
So in rightmost derivation, we read the input string from right to left.

Example:
Consider the grammar SS+S, SS*S, Sa, Sb.

Derive the string w=a*a+b.

S⟹S+S
S⟹S+b
S⟹S*S+b
S⟹S*a+b
S⟹a*a+b

Classification of CFG

Context Free Grammars (CFG) can be classified on the basis of following two
properties:

1) Based on number of strings it generates:

 If CFG is generating finite number of strings, then CFG is Non-Recursive (or the
grammar is said to be Non-recursive grammar)
 If CFG can generate infinite number of strings then the grammar is said to
be Recursive grammar.
Examples of Recursive Grammar
1) S->SaS
S->b
The language(set of strings) generated by the above grammar is :{b, bab, babab,...}, which
is infinite.
2) S-> Aa
A->Ab|c
The language generated by the above grammar is :{ca, cba, cbba ...}, which is infinite.

Types of Recursive Grammars

Based on the nature of the recursion in a recursive grammar, a recursive CFG can be
again divided into the following:
 Left Recursive Grammar (having left Recursion)
 Right Recursive Grammar (having right Recursion)
 General Recursive Grammar(having general Recursion)

Example of Non-Recursive Grammar

S->Aa
A->b|c
The language generated by the above grammar is :{ba, ca}, which is finite.

2) Based on number of derivation trees:

 If there is only 1 derivation tree then the CFG is unambiguous.
 If there are more than 1 left most derivation tree or right most derivation or parse tree ,
then the CFG is ambiguous .

During Compilation, the parser uses the grammar of the language to make a parse tree(or
derivation tree) out of the source code. The grammar used must be unambiguous. An
ambiguous grammar must not be used for parsing.

Example of an Unambiguous CFG:

Consider the CFG for a simple arithmetic expression involving addition and multiplication:
E→E+T ∣ T
T→T×F ∣ F
F→(E) ∣ id
This grammar ensures that:
 The addition operation is done after multiplication.
 There is only one valid way to parse an expression.

For example, for the expression a+b×c , the only valid parse is that multiplication happens
first due to the structure of the grammar. This is an unambiguous grammar because there is
only one way to derive the string.

Example of an Ambiguous CFG:

Consider the following CFG for arithmetic expressions:
E→E+E ∣ E×E ∣ id
This grammar does not specify operator precedence. For the string a+b×c , there are two
possible derivation trees:
1. a+(b×c)
2. (a+b)×c
Both derivations are valid according to the grammar, but they represent different
interpretations of the same string, leading to ambiguity.
Note: A linear grammar is a context-free grammar that has at most one non-terminal in the
right hand side of each of its productions.

Derivation Tree or Parse Tree: If W is a string in the context free grammar G .W Є

L(G).Then the derivation of W is represented a tree is called derivation tree or parse tree.
In the derivation tree we have
1. The starting sumbol S is the root.
2. All the internal nodes in the parse tree are variable.
3. All the leaf nodes are terminals.
4. If we write all the leaf nodes of the tree from left to right we get a string , that string
is called “Derivation “ or “Yield” of that tree.

Ambiguous Grammar: A Grammar G is said to be ambiguous if there exist a string W

belongs to L(G) has two or more left derivations or two or more right derivations such
grammar is called ambiguous grammar.
Example: AA+A|A-A|a W=a+a-a
Left Most Derivation (LMD) -1 : AA+A Left Most Derivation(LMD) -2 : AA-A
AA+a AA+A-A
Aa+A-A Aa+A-A
Aa+a-A Aa+a-A
Aa+a-a Aa+a-a

A A

A - A
A + A

A + A

a A - A
a a a

a a
Parse Tree for the above derivation: Parse Tree for the above derivation:
There exist two left derivations , So the given grammar is ambiguous.

Example 2:
S→0S1∣SS∣ϵ
Answer: It’s ambiguous because at least one string in its language has two distinct parse trees
(equivalently, two distinct leftmost derivations).
Take the string 01.

Take the string 0011

 So, 0011 has two distinct parse trees, one nested and one concatenated — which
proves the grammar is ambiguous.

Example 3:
S→aAB
A→bC | cd
C→cd
B→c | d
Ambiguous grammar: a context-free grammar is ambiguous if there exists at least one string
in its language that has two distinct parse trees (equivalently two distinct leftmost or rightmost
derivations).
 Left Recursion: A grammar is said to be Left recursive if and only if it is of the form AAα
such that A is a variable, and α Є (VUT)*.
Example: SS+S
SSa

Elimination of Left Recursion: Consider the grammar G is in the form

AA α1|A α2....A αn|β1| β2... βm , where β1, β2... βn doesn’t starts with A. It is said to be
Left Recursive production. This can be eliminated by introducing the following
productions.
A β1A1| β2A1.......| βmA1
A1 α1 A1| α2A1.......| αnA1| Є
Examples:
1. Consider the CFG SS+S|S*S|a|b eliminate the left recursion if any .
Sol: SS+S|S*S|a|b is in the form of AA α1|A α2....A αn|β1| β2... βm so it is in left
recursion.
After eliminating left recursion, the required grammar is
SaS1|bS1
S1+SS1|*SS1| Є
2. Consider the SAa|b, AAc|Sd| Є eliminate the left recursion if any .
Sol: SAa|b
AAc|Sd| Є
In the production of A replace S with SAa|b then
AAc|Aad|bd| Є
SAa|b
In production A we have Left recursion , so eliminate Left recursion.
AbdA1|A1
A1cA1|adA1| Є
After elimination of left recursion the required Grammar is
SAa|b
AbdA1|A1
A1cA1|adA1| Є
Left Factoring: Two or more productions of a variable A of the grammar G is said to be
left factoring if all the productions of the form
Aα β1| α β2|..... α βn where βi Є(VUT)* and βi doesn’t starts with α then all the
productions are said to have common left factor α example
Sab|ac|ad Here a is called common left factor.

Elimination of Left Factoring: Consider the A productions which are having the left
factoring as follows
Aα β1| α β2|..... α βn| γ1| γ2 ......| γm
γ 1, γ2 ........ γm doesn’t starts with α
we can eliminate left factoring in the following way
A αA1| γ1| γ2 ......| γm
A1β1|β2.......βm.
Examples:
1. Consider the CFG SaSa|aa|b eliminate left factoring.
Sol: In the given grammar there exist left factoring . a is common left factoring. We can
eliminate left factoring in following way.
SaA1|b
A1 Sa|a
Simplification of Grammars:
Grammar may contain some extra symbols , these will increase the length of the
grammar. Elimination of these unnecessary symbols is called simplification of CFGs.
Simplification of grammars generally includes
a. Elimination of useless symbols.
b. Elimination of Є productions.
c. Elimination of unit productions of the form AB.
a. Elimination of useless symbols: A symbol is useless if it can not derive a terminal
or it is not reachable from start symbol.
Examples:
1. Eliminate useless symbols and productions from the following grammar.
SABa|BC, AaC|BCC, Ca, Bbcc, DE, Ed, Fe
Sol: In the given grammar the non terminals D,E,F are not reachable from the start symbol
‘S’, so we can eliminate them And the simplified grammar is
SABa|BC, AaC|BCC, Ca, Bbcc,
2. Eliminate useless symbols in G.
SAB|CA, SBC|AB, Aa, CaB|b.
Sol: In the given grammar there is no production for B. So we have to eliminate the
productions which contains B.
The simplified grammar is
SCA
Aa
Cb.

3. Eliminate useless symbols in G. SaAa, AbBB, Bab, Cab.

Sol: In the Given grammar the variable C is not derived from the start symbol ‘S’. So ‘C’
is useless.
The simplified grammar is
SaAa,
AbBB,
Bab.

b. Elimination of Є productions:
If some CFL contains the word Є then CFG must have a Є-production. However if a
CFG has a Є-production then the CFL doesn’t necessarily contain Є.
Example: SaX
XЄ
CFL={a}
Nullable Variables: In a given Context free grammar a non terminal X is nullable if
1. There is a production XЄ
2. There is a derivation that starts at X and leads to Є
i.e X-----Є

Procedure for eliminating Є – productions:

Step 1: Construct set Vn of all nullable variables.
Step 2: For each production BA, if A is nullable variable, replace nullable variable
by Є and add with all possible combinations on the RHS.
Step 3: Do not add the production Aε .

Examples:
1. Eliminate Є-productions from the following grammar G.
SABaC, ABC, Bb|ε, CD|ε, Dd.
Sol: nullable variable are Vn = {B,C,A}
Because B, C are having Є-productions and production A leads to Є.
Now we have to replace the nullable variable with Є.
 SABaC|AaC|ABa|aC|a|Aa|Ba
ABC|B|C
CD
Bb
Cd.
2. Eliminate Є-productions from the following grammar G.
SaA, ABB, BaBb|Є
Sol: nullable set Vn= {B}
SaA|a
ABB|B
BaBb|ab.
c. Elimination of unit productions: A production which is of the form AB where A,
B are variables is said to be unit productions.
For each pair of non-terminals A and B such that there is a production AB and
the non-unit productions from B are BS1|S2|...Sn
Where Si Є(TUV)* are strings of terminals and non-terminals then create new
productions as
AS1|S2|...Sn
Do the same for all such pairs A and B simultaneously.
Examples:
1. Eliminate the unit productions in the grammar
SA|bb, AB|b, BS|a
Sol: In the given grammar we have following unit productions
SA, AB, BS.
After eliminating the above unit productions, the required grammar is as follows.
Sb|bb|a
Ab|bb|a
Ba|bb|b

2. Eliminate the unit productions in the grammar

SAa|B
BA|bb
Aa|bc|B
Sol: In the given grammar we have following unit productions
SB, BA, AB.
After eliminating the above unit productions, the required grammar is as follows.
SAa|a|bc|bb
Bbb|a|bc
Aa|bc|bb.
Problems:
* Simplify the grammar SaA|aBB, AaAA|Є,BbB|bbC, CB.
Sol: Removing Є-productions gives resulting grammar as
SaA|a|aBB
AaAA|aA|a
 BbB|bbc
CB
Eliminating unit productions we get the resulting grammar as
SaA|a|aBB
AaAA|aA|a
BbB|bbc
CbB|bbC
B and C are identified as useless symbols. Eliminate these we get
SaA|a
AaAA|aA|a
Finally the reduced grammar is SaA|a, AaAA|aA|a which defines any number of a’s

Normal Forms:
If G is a Context free grammar and the production of G satisfy certain properties
then G is said to be in a normal form. There are two types of normal forms.
1. Chomsky Normal Form (CNF)
2. Greibach Normal Form (GNF)
1. Chomsky's Normal Form (CNF)
CNF stands for Chomsky normal form. A CFG(context free grammar) is in
CNF(Chomsky normal form) if all production rules satisfy one of the following conditions:
 A non-terminal generating two non-terminals. For example, S → AB.
 A non-terminal generating a terminal. For example, S → a.
For example:
1. G1 = {S → AB, S → c, A → a, B → b}
2. G2 = {S → aA, A → a, B → c}
The production rules of Grammar G1 satisfy the rules specified for CNF, so the
grammar G1 is in CNF. However, the production rule of Grammar G2 does not satisfy the
rules specified for CNF as S → aA contains terminal followed by non-terminal. So the
grammar G2 is not in CNF.

Steps for converting CFG into CNF

Step 1: In the grammar, remove the null(ε), unit and useless productions. You can refer to
the Simplification of CFG.

Step 2: Eliminate terminals from the RHS of the production if they exist with other non-
terminals or terminals. For example, production S → aA can be decomposed as:
1. S → RA
2. R → a
Step 3: Eliminate RHS with more than two non-terminals. For example, S → ASB can be
decomposed as:
1. S → RS
2. R → AS

Example:
Convert the given CFG to CNF. Consider the given grammar G1:
1. S → a | aA | B
2. A → aBB | ε
3. B → Aa | b

Solution:

Step 1: As grammar G1 contains A → ε null production, its removal from the grammar
yields:
S → a | aA | B
A → aBB
B → Aa | b | a
Now, as grammar G1 contains Unit production S → B, its removal yield:
S → a | aA | Aa | b
A → aBB
B → Aa | b | a
Also remove the unit production S1 → S, its removal from the grammar yields:
S → a | aA | Aa | b
 A → aBB
B → Aa | b | a
Step 2: In the production rule S → aA | Aa, A → aBB and B → Aa,
terminal a exists on RHS with non-terminals. So we will replace terminal a with X:
S → a | XA | AX | b
A → XBB
B → AX | b | a
X→a
Step 3: In the production rule A → XBB, RHS has more than two symbols, removing it
from grammar yield:

S → a | XA | AX | b
A → RB
B → AX | b | a
X→a
R → XB
Hence, for the given grammar, this is the required CNF.

2. Greibach Normal Form (GNF)

GNF stands for Greibach normal form. A CFG(context free grammar) is in
GNF(Greibach normal form) if all the production rules satisfy one of the following
conditions:
 A non-terminal generating a terminal. For example, A → a.
 A non-terminal generating a terminal which is followed by any number of non-
terminals. For example, S → aASB.

For example:
1. G1 = {S → aAB | aB, A → aA| a, B → bB | b}
2. G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}
The production rules of Grammar G1 satisfy the rules specified for GNF, so the
grammar G1 is in GNF. However, the production rule of Grammar G2 does not satisfy the
rules specified for GNF as A → ε and B → ε contains ε(only start symbol can generate ε).
So the grammar G2 is not in GNF.

Steps for converting CFG into GNF

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

Step 2: If the grammar exists left recursion, eliminate it.

If the context free grammar contains 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:
1. S → XB | AA
 2. A → a | SA
3. B → b
4. X → a

Solution:
As the given grammar G is already in CNF and there is no left recursion, so we can
skip step 1 and step 2 and directly go to step 3.
The production rule A → SA is not in GNF, so we substitute S → XB | AA in the
production rule A → SA as:
1. S → XB | AA
2. A → a | XBA | AAA
3. B → b
4. X → a
The production rule S → XB and A → XBA is not in GNF, so we substitute X → a in the
production rule S → XB and A → XBA as:
1. S → aB | AA
2. A → a | aBA | AAA
3. B → b
4. X → a
Now we will remove left recursion (A → AAA), we get:
1. S → aB | AA
2. A → aC | aBAC
3. C → AAC | ε
4. B → b
5. X → a
Now we will remove null production C → ε, we get:
1. S → aB | AA
2. A → aC | aBAC | a | aBA
3. C → AAC | AA
4. B → b
5. X → a
The production rule S → AA and C → AA is not in GNF, so we substitute A → aC | aBAC
| a | aBA in production rule S → AA and C → AA as:
1. S → aB | aCA | aBACA | aA | aBAA
2. A → aC | aBAC | a | aBA
3. C → AAC
4. C → aCA | aBACA | aA | aBAA
5. B → b
6. X → a
The production rule C → AAC is not in GNF, so we substitute A → aC | aBAC | a | aBA
in production rule C → AAC as:
1. S → aB | aCA | aBACA | aA | aBAA
2. A → aC | aBAC | a | aBA
3. C → aCAC | aBACAC | aAC | aBAAC
4. C → aCA | aBACA | aA | aBAA
5. B → b
6. X → a
Hence, this is the GNF form for the grammar G.