Chapter Three

Context Free grammar and languages

 Context-Free Grammars (CFG)
 Limitations of finite automata
 There are languages, such as {0𝑛 1𝑛 |n>=0} that cannot be described (specified) by finite automata
and regular expression.

 Context-free grammars provide a more powerful mechanism for language

specification.

 Context-free grammars can describe features that have a recursive structure

making them useful beyond finite automata.

 Context-free grammars are used as basis for compiler design and implementation

 Context-free grammars are used as specification mechanisms for programming

language.
 Context-free languages
 The collection of languages specified by context-free grammars are called
context-free language.

 Context-free languages include regular languages and many others.

 Here we will study the formal concepts of context-free grammars and context-free
languages.

Notations : Abbreviate the phrase context-free grammar to CFG.

Abbreviate the phrase context-free language to CFL

 Definition of Context-Free Grammar
A GFG (or just a grammar) G is a tuple G = (V, T, P, S) where

1. V is the (finite) set of variables (or nonterminal or syntactic categories). Each variable
represents a language, i.e., a set of strings

2. T is a finite set of terminals, i.e., the symbols that form the strings of the language being
defined

3. P is a set of production rules that represent the recursive definition of the language.

4. S is the start symbol that represents the language being defined. Other variables represent
auxiliary classes of strings that are used to help define the language of the start symbol.
 Definition of Context-Free Grammar
Production rules Each production rule consists of:
1. A variable that is being (partially) defined by the production. This variable is often
called the head of the production.

2. The production symbol →.

3. A string of zero or more terminals and variables. This string, called the body of the
production, represents one way to form strings in the language of the variable of the
head. In doing so, we leave terminals unchanged and substitute for each variable of
the body any string that is known to be in the language of that variable
 Example of CFG
1. write a Context-Free Grammar (CFG) for palindromes over the alphabet {0, 1}?
• A string w over an alphabet Σ is a palindrome if W=𝑊 𝑟
Solution
• V (Variables): {p}
• Σ (Terminals): {0, 1, ε} (assuming ε represents the empty string)
• S (Start symbol): p
• Production (p):

1. p→0 Note : the first production rules 1,2,3 are base for palindrome.
2. p→1 4,5 Wrap the same symbol around a smaller palindrome
3. p→ε
4. p → 0p0
5. p → 1p1.

This grammar correctly generates all binary palindromes, including ε, 0, 1, 00, 11, 010, 101, 0110, etc.
 Example of CFG
Try to Derive “1010000101” using our CFG to check whether the string is W = 𝑊 𝑅
1. p⇒
2. p⇒ 1p1( rule 5)
3. p⇒ 1 0p0 1( rule 4)
4. p⇒ 1 0 1p1 0 1(rule 5)
5. p⇒ 1 0 1 0p0 1 0 1(rule 4)
6. p⇒ 1 0 1 0 0p0 0 1 0 1(rule 4)
7. p⇒ 1 0 1 0 0 ε 0 0 1 0 1(rule 3)

Confirm
• Starts and ends with 1
• Moves inward with matching pairs
• Middle is ε → so even length
• So:
• 1010000101 is successfully generated by the CFG and is a palindrome
 Example of CFG
2. Write context free grammar 0𝑛 1𝑛 |n>=0?
L={0𝑛 1𝑛 |n>=0}

This means:

• The string contains n 0s followed by n 1s

• Both numbers of 0s and 1s are equal

• Examples: ε, 01, 0011, 000111, 00001111, etc.

Context-Free Grammar (CFG) for L = {0ⁿ1ⁿ | n ≥ 0}

Example Derivation for 000111:
Let’s define:
1. S(start symbol)
• V (Variables): {S}
2. S⇒ 0S1(rule 2)
• T(Terminals): {0, 1}
3. S ⇒ 0(0S1)1 = 00S11(rule 2)
• S (Start symbol): S
1. S → ε 4. S ⇒ 00(0S1)11 = 000S111(rule 2)
• P (Production Rules):
2. S → 0S1 5. S ⇒ 000ε111 = 000111(rule 1)
 Example of CFG
3. write context free grammar for the given language?

L = {aⁿbⁿcᵐdᵐ | n ≥ 1, m ≥ 1}

This means:

• The number of a's must equal the number of b's (n ≥ 1),

• The number of c's must equal the number of d's (m ≥ 1),

• a’s and b’s come before c’s and d’s,

Some example strings:

L = {ab cd, aabb ccdd, aaabbbccdd……}

abb (❌ no match),
 Example of CFG
CFG for L = {aⁿbⁿcᵐdᵐ | n ≥ 1, m ≥ 1}

Let’s break it into two parts and then combine them.

Grammar Components:

We'll use two sub-productions:

– X generates aⁿbⁿ with n ≥ 1

– Y generates cᵐdᵐ with m ≥ 1

CFG Definition:

• Variables (V): {S, X, Y}

• Terminals (Σ): {a, b, c, d}

• Start symbol: S
1. S → XY // Main start rule
• Production rules: 2. X → aXb | ab // Generates at least one a-b pair (n ≥ 1)
3. Y → cYd | cd // Generates at least one c-d pair (m ≥ 1)
 Example of CFG
Example: Derivation for aabbccdd
S(start state)
S⇒ XY (rule 1)
S⇒ aXbY (rule 2) X ⇒aXb
S⇒ aabbY (rule 2) X ⇒ ab
S⇒ aabb cYd (rule 3 ) Y ⇒cYd
S ⇒ aabb ccdd (rule 3)Y ⇒cd
S ⇒ aabbccdd
 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:
 We have to decide the non-terminal which is to be replaced.
 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 replaced with production rule.
1. Left-most Derivation
In the left most derivation, the input is scanned and replaced with the production rule from left
to right. So in left most derivatives we read the input string from left to right.
2. Right-most Derivation
In the right most derivation, the input is scanned and replaced with the production rule from
right to left. So in right most derivatives we read the input string from right to left.
 Derivation
Example 1 :Deriving LMD and RMD of a given input string a - b + c from a given CFG
Variable ={S}
Terminal ={a,b,c,+,-}
Start symbol ={ S }
Production rules:
S = S + S (1)
S = S - S (2)
S = a | b |c (3)
Derivation Steps (Leftmost): Derivation Steps (Leftmost):
S S
S→S+S Apply S→S+S
→ S+S → S+S
Leftmost S→S−S Rightmost S→c
→ S−S+S → S+c
Leftmost S→a Left S→S−S
→ a−S+S → S−S+c
Next leftmost S→b Rightmost S→b
→ a−b+S → S−b+c
Final S→c Leftmost (now only one S) S→a
→ a−b+c → a−b+c
 Derivation
Example 2 :Deriving LMD and RMD of a given input string ‘’aabaaaba’’ from a given CFG
Variable ={S,T}
Terminal ={a,b}
Start symbol ={ S}
Production rules:
S → ST ∣ aTa
T → S∣aTa∣b
Derivation Steps (Leftmost):
S ⇒ ST Derivation Steps (Rightmost):
⇒ aTaT S ⇒ ST
⇒ aaTaaT ⇒ SaTa
⇒ aabaaT ⇒ Saba
⇒ aabaaaTa ⇒ aTaaba
⇒ aabaaaba ⇒ aaTaaaba
⇒ aabaaaba ⇒ aabaaaba
⇒ aabaaaba
 Derivation
Exercises
Consider the following grammar:
S → AS | ε.
S → aa | ab | ba | bb
Give leftmost and rightmost derivations of the string aabbba.
 Parse tree
 Parse tree is the graphical representation of symbol. The symbol can be terminal
or non-terminal.
 In parsing, the string is derived using the start symbol. The root of the parse tree
is that start symbol.
 It is the graphical representation of symbol that can be terminals or non-
terminals.
 Parse tree follows the precedence of operators. The deepest sub-tree traversed
first. So, the operator in the parent node has less precedence over the operator in
the sub-tree.
 If an interior node is labeled with a non terminal A and finally strings are read
from left to right.
 Parse tree
The parse tree follows these points:
 All leaf nodes have to be terminals.
 All interior nodes have to be non-terminals.
 In-order traversal gives original input string.
Example : CFG
E → N ∣ E*E ∣ E/E ∣ E+E ∣ E-E ∣ (E)
N → DN ∣ D
D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9
Create parse tree for architmetic expression 3+8*7
 Parse tree
Derivation parse tree

E ⇒ E+E

⇒ E+E*E

⇒N+E*E

⇒ D+E*E
 Parse tree
Derivation parse tree

⇒ 3+E*E

⇒ 3+N*E

⇒ 3+D*E
 Parse tree
Derivation parse tree

⇒ 3+8*E

⇒ 3+8*N

⇒ 3+8*D
 Parse tree
Derivation parse tree

⇒ 3+8*7

⇒ 3+8*7
 Parse tree
Example 2
Consider the CFG grammar
S aSa | a | b| Є
Now for input string ‘aabaa’
We have,
S aSa
S aaSaa
S aabaa So the parse tree for
‘’aabaa’’
Parse tree
Exercises
 Ambiguity
A Grammar G = (V, T, P and S) is said to be ambiguous if there is a string w ε L
(G) for which we can derive two or more distinct derivation tree rooted at S and
yielding w. In other words, a grammar is ambiguous if it can produce more than
one leftmost or more than one rightmost derivation for the same string in the
language of the grammar.

Equivalent statements about a CFG G

 1. G is ambiguous if a word in L(G) has two different parse trees

 2. G is ambiguous if a word in L(G) has two different left-most derivations

 3. G is ambiguous if a word in L(G) has two different right-most derivations

Note. It is not the case that G is ambiguous if a word merely has two different
derivations

.
 Ambiguity
Example
S  AB |aaB
A  a | Aa
Bb
For string aab;
We have two leftmost derivations as;
SAB
AaB
LMD 1
aaB
 aab
 aab
Also,
S aaB LMD 2
aab
 aab
 Ambiguity
Example 2
E E+E
E E*E
E id ,String id+id*id
LMD 1 RMD 1 Parse tree

E E*E E E*E

E+E*E E*id

id+ E*E E+E*id

id+ id*E E+id*id

id+ id*id id+id*id

 Ambiguity
Example 2
E E+E
E E*E
E id ,String id+id*id
LMD 2 RMD 2 Parse Tree 2
E E+E E E+E

id+E E+E*E

id+ E*E E+E*id

id+ id*E E+id*id

id+ id*id id+id*id

Note the above string ‘’ id+id*id’’ has more than one LMD, RMD and parse tree , so the
given grammar is ambiguous
 Sentential forms
 Derivations from the start symbol produce strings that have a special role. We call these
sentential forms. i.e. if G=(V,T,P,S) is a CFG,
 A sentential form is any string made up of variables and/or terminals that can be derived
from the start symbol S using production rules.
 If you use leftmost derivations (always replace the leftmost variable first), you get a left
sentential form.
 If you use rightmost derivations (always replace the rightmost variable first), you get a
right sentential form.
Note: Language L(G)
 L(G) is the set of strings you can get from S that are made only of terminals (no
variables left).
 So: only the sentential forms that have only terminals are part of the language L(G).
 Normal forms and Simplification of CFG
 The goal of this section is to show that every context free language (without Є) is
generated by a CFG in which all production are of the form A BC or A a, where
A,B and C are variables, and a is terminal. This form is called Chomsky Normal Form.
To get there, we need to make a number of preliminary simplifications, which are
themselves useful in various ways;

 We must eliminate ―useless symbols‖: Those variables or terminals that do not

appear in any derivation of a terminal string from the start symbol.
 We must eliminate ―Є-production‖: Those of the form A Є for some variable
A.
 We must eliminate ―unit production: Those of the form A B for variables A
and B.
 Eliminating Useless Symbols:
Thus useful symbols are those variables or terminals that appear in any derivation
of a terminal string from the start symbol. Eliminating a useless symbol includes
identifying whether or not the symbol is ―generating and ―reachable.
Generating Symbol:

 A symbol is generating if you can start from it and finally reach only terminals.

 Every terminal is always generating, because it already is a terminal.

Reachable symbol: A symbol is reachable if you can get to it by starting from the start
symbol S using the grammar rules.
Procedure to remove useless symbols:
• First remove non-generating symbols (symbols that cannot lead to only terminals).
• Then remove non-reachable symbols (symbols that you can never reach from the start).

Thus if we eliminate the non-generating symbols and then non-reachable, we shall

have only the useful symbols left.
 Eliminating Useless Symbols:
Example
Consider a grammar defined by following productions:
SaB | bX
A Bad | bSX | a
B aSB | bBX
XSBd | aBX | ad

Here;
 A and X can directly generate terminal symbols. So, A and X are generating
symbols. As we have the productions A a and X ad.
 Also,
S bX and X generates terminal string so S can also generate terminal string.
Hence, S is also generating symbol.
B can not produce any terminal symbol, so it is non-generating.
Hence, the new grammar after removing non-generating
symbols is:
S bX
A bSX | a
X ad
 Eliminating Useless Symbols:
Here,
 A is non-reachable as there is no any derivation of the form S* α A β
in the grammar. Thus eliminating the non-reachable symbols, the
resulting grammar is:
S bX
X ad
This is the grammar with only useful symbols.
Exercise
1) Remove useless symbol from the following grammar:
S xyZ | XyzZ
XXz | xYZ
YyYy | XZ
Z Zy | z
1) Remove useless symbol from the following grammar
S aC | SB
A bSCa
BaSB | bBC
C aBc | ad
 Eliminating Є-productions:

A grammar is said to have Є-productions if there is a production of the form A Є. Here

our strategy is to begin by discovering which variables are ―nullable. A variable ‘A‘ is
nullable if A * Є.
Algorithm (Steps to remove Є-production from the grammar):
 If there is a production of the form A Є, then A is ―nullable.
 If there is production of the form B X1, X2. And each Xi‘s are nullable
then B is also nullable.
 Find all the nullable variables.
 If B X1, X2……………. Xn is a production in P then add all productions P‘
formed by striking out some subsets of there Xi‘s that are nullable.
 Do not include B Є if there is such production.
 Eliminating Є-productions:
Example:
Consider the grammar:
SABC
A BB | Є
B CC | a
C AA | b
Here,
A Є A is nullable.
CAA* Є, C is nullable
B CC* Є, B is nullable
SABC* Є, S is nullable
Now for removal of Є –production: In
production
SABC, all A, B and C are nullable. So,
striking out subset of each the possible
combination of production gives new
productions as:
S ABC | AB | BC | AC | A | B | C
Similarly for other can be done and the resulting grammar after removal of e-production is:
SABC | AB | BC | AC | A | B | C
ABB | B
BCC | C | a
CAA | A | b
 Eliminating Unit Production:
:
A unit production is a production of the form A B, where A and B are both
variables. Here, if A B, we say B is A-derivable. B C, we say C is B-
derivable.
Thus if both of two A B and BC, then A* C, hence C is also A-derivable.
Here pairs (A, B), (B, C) and (A, C) are called the unit pairs.

To eliminate the unit productions, first find all of the unit pairs. The unit
pairs are; (A, A) is a unit pair for any variable A as A* A
If we have A B then (A, B) is unit pair.
If (A, B) is unit pair i.e. AB, and if we have B C then (A, C) is also a unit pair.

Now, to eliminate those unit productions for a, gives grammar say G = (V, T, P, S),
we have to find another grammar G‘ = (V, T, P‘, S) with no unit productions. For
this, we may workout as below;
 Initialize P‘ = P
 For each A ε V, find a set of A-derivable variables.
 For every pair (A, B) such that B is A-derivable and for every non-unit
production B α, we add production A  α is P‘ if it is not in P‘ already.
 Delete all unit productions from P‘.
 Eliminating Unit Production:
:
Example
Remove the unit production for grammar G defined by productions:
P = {S S + T | T
T T* F | F
F (S) | a
};
Initialize
 P‘ = {S S + T | T
T t*F | F
F (S) | a }
• Now, find unit pairs;
Here, S T So, (S, T) is unit pair.
T F So, (T, F) is unit pair.
Also, ST and T F So, (S, F) is unit pair.

• Now, add each non-unit productions of the form B α for each pair
(A, B); P‘ = {
SS + T |T * F| (S) | a
TT * F | (S) | a | F
F (S) | a
}
 Eliminating Unit Production:
Delete the unit productions from
:
the grammar;

P‘ = {
S S + T | T * F | (S) | a
T T * F | (S) | a
F (S) | a

Exercise
 Simply the grammar G = (V, T, P, S) defined by following productions.
S ASB | Є
A aAS | a
B SbS | A | bb | Є
• Simplify the grammar defined by following production:
S 0A0 | 1B1 | BB
A C
B S | A
CS | Є
Note: Here simplify means you have to remove all the useless symbol, Unit production and Є-productions.
 Chomsky normal form
• One of the simplest and most useful simplified forms of CFG is called the
Chomsky normal form.
• In CNF, every production must be of the form:
– A → BC (two variables) or
– A → a (one terminal)
• No mixing terminals and variables in a single production (except if
directly A → a).
• Any context-free language is generated by a context-free grammar
in Chomsky normal form.
• Show that any CFG can be converted into Chomsky normal form
• Conversion procedure has several stages where the rules that violate
Chomsky normal form conditions are replaced with equivalent rules
that satisfy these condition
 Chomsky normal form
Step 1: add a new start symbol S’ to P, and the rule S’ −→ S to P

Note: this change guarantees that the start symbol of G′ does not occur on the rhs

of any rule.

Step 2: eliminate null-production

Step 3: remove unit production

Step 4: Reduce Productions with More Than Two Non-Terminals

Eliminate RHS with more than two non-terminals. e.g,; production rule A→BCD can
be decomposed as: A→XD, X→BC

Step 5: Replace Terminals in Mixed Productions

Eliminate terminals from RHS if they exist with other terminals or non-terminals. e.g. ,
production rule A→ aB can be decomposed as: A→YB, Y→a.
 Chomsky normal form
Example CFG conversion Consider the grammar G whose rules are:
S −→ ASA|aB
A −→ B|S
B −→ b| ε
Notation: symbols removed are green and those added are red.
1. After first step of transformation we get
S’−→ S
S −→ ASA|aB
A −→ B|S
B −→ b| ε
2. Removing ε rules Removing
B→ε
: S’ −→ S
S −→ ASA|aB|a
A −→ B|S|ε
B −→ b| ε
 Chomsky normal form
Removing A → ε :
S’ −→ S
S −→ ASA|aB|a|SA|AS|S
A −→ B|S| ε
B −→ b
3. Removing unit rule
Removing S → S:
S’ −→ S
S −→ ASA|aB|a|SA|AS|S
A −→ B|S
B −→ b
 Chomsky normal form
Removing S’→ S:
S’ −→ ASA|aB|a|SA|AS
S −→ ASA|aB|a|SA|AS
A −→ B|S
B −→ b
Removing A → B:
S’ −→ ASA|aB|a|SA|AS
S −→ ASA|aB|a|SA|AS
A −→ b|S
B −→ b
Removing A → S:
S’−→ ASA|aB|a|SA|AS
S −→ ASA|aB|a|SA|AS
A −→ b|ASA|aB|a|SA|AS
B −→ b
 Chomsky normal form
4. Reduce Productions with More Than Two Non-Terminals
S’−→ ASA|aB|a|SA|AS
S −→ ASA|aB|a|SA|AS
A −→ b|ASA|aB|a|SA|AS
B −→ b
From here S’−→ ASA, S−→ASA, A−→ ASA, productions have more than two variables
so ASA decompose to S’−→ AX, X−→SA, apply for both remaining productions
S’−→ AX|aB|a|SA|AS
S −→ AX|aB|a|SA|AS
A −→ b|AX|aB|a|SA|AS
B −→ b
X −→SA
 Chomsky normal form
5. Replace Terminals in Mixed Productions(terminal and non-terminal)
S’−→ AX|aB|a|SA|AS
S −→ AX|aB|a|SA|AS
A −→ b|AX|aB|a|SA|AS
B −→ b
X −→SA
Then S −→aB, decompose to S −→ YB, Y −→a
Finally, we get:
S’−→ AX|YB|a|SA|AS
S −→ AX|YB|a|SA|AS
A −→ b|AX|YB|a|SA|AS
B −→ b
X −→SA
Y −→a
 Greibach Normal Form
• A CFG is in Greibach Normal Form (GNF) if all production
rules satisfy one of the following conditions:
• A non-terminal generating a terminal (e.g., A→b)
• A non-terminal generates a terminal followed by any number
of non-terminals (e.g., A→bC1C2…CN​)
• Where A and C are non terminals and b is also terminal.
 Greibach Normal Form
How to Convert CFG to GNF

Step 1. If the given grammar is not in CNF, convert it to CNF. You can refer following article to convert
CFG to CNF:

Step 2. Change the names of non terminal symbols to A1 till AN in same sequence.

Step 3. Check for every production rule if RHS has first symbol as non terminal say Aj for the production
of Ai, it is mandatory that i should be less than j. Not great and not even equal.
– If i> j then replace the production rule of Aj at its place in Ai.

– If i=j, it is the left recursion. Create a new state Z which has the symbols of the left recursive production, once
followed by Z and once without Z, and change that production rule by removing that particular production
and adding all other production once followed by Z.

Step 4. Replace very first non terminal symbol in any production rule with its production until
production rule satisfies the above conditions.

For converting a CNF to GNF always move left to right for renaming the variables.
 Greibach Normal Form
Example: Suppose this the production and we need to convert it into GNF.
S → CA|BB
B → b|SB
C→ b
A→a
For converting a CNF to GNF first rename the non terminal symbols to A1,A2 till AN in
same sequence as they are used.
A1 = S
A2 = C
A3 = A
A4 = B
Therefore, now the new production rule is,
A1 → A 2 A3 | A 4 A4
A2 → b
A3 → a
A4 → b | A1A4
 Greibach Normal Form
• Now, check for every production Ai → Aj X, where X can be any number of
terminal symbols. If i<j in the production then it is good to go to the next step but if
i>=j then change the production by replacing it with that terminal symbol’s
production. if i=j then it is a left recursion and you need to remove left recursion.

• Here for A4, 4 !< 1, so now replace it with A1‘s production rule.
A 1 → A 2 A3 | A 4 A4
A2 → b
A3 → a
A 4 → b | A2 A3 A 4 | A4 A4 A 4 ,
 Greibach Normal Form
still A4, 4!<2 so now replace it with A2 ‘s production rule
A1 → A2A3 | A4A4
A2 → b
A3 → a
A4 → b | bA3A4 | A4A4A4

Here A4A4A4 in production rule of A4 is the example of left recursion.

To replace the left most recursion take a new Non terminal symbol Z, which has the X
part or the trailing part of the left most recursive production once followed by Z and
once without Z. Here in A4A4A4, the part after the first A4 is A4A4, therefore
 Greibach Normal Form
Z → A4A4 | A4A4Z
Now change the above production rule by putting Z after every previous production of
that Ai, and remove the left recursive production.
A1 → A2A3 | A4A4
A2 → b
A3 → a
A4 → b | bA3A4 | bZ | bA3A4Z
Z → A4A4 | A4A4Z
The Last step is to replace the production to the form of either
Ai → b (any single terminal symbol)
OR
Ai → bC (any single terminal followed by any number of non terminals)
So here we need to replace A2 in production rule of A1 and so on.
A1 → A2A3 | A4A4
A2 → b
A3 → a
A4 → b | bA3A4 | bZ | bA3A4Z
Z → A4A4 | A4A4Z
 Greibach Normal Form
A1 → bA3 | bA4 | bA3A4A4 | bZA4 | bA3A4ZA4
A2 → b
A3 → a
A4 → b | bA3A4 | bZ | bA3A4Z
Z → bA4 | bA3A4A4 | bZA4 | bA3A4ZA4 | bA4Z | bA3A4A4Z | bZA4Z | bA3A4ZA4Z

Here is the Final GNF:

A1 → bA3 | bA4 | bA3A4A4 | bZA4 | bA3A4ZA4

A2 → b
A3 → a
A4 → b | bA3A4 | bZ | bA3A4Z
Z → bA4 | bA3A4A4 | bZA4 | bA3A4ZA4 | bA4Z | bA3A4A4Z | bZA4Z | bA3A4ZA4Z