VNW Ce Toc Un 03

Program: BE (Computer Engineering & Information Technology)
Class: TE
Course: Theory of Computation
Unit 03: Context Free Grammars & Languages
Generation of Derivation Tree / Parse Tree
❑ A derivation tree or parse tree is an ordered rooted tree that

graphically represents the semantic information a string derived from
a context-free grammar.
❑ Representation technique.
1. Root Vertex: Must be labeled by the start symbol.
2. Vertex: Labeled by a non-terminal symbol.
3. Leaves: Labeled by a terminal symbol or ε.
❑ If S → x1x2 …… xn is a production rule in a CFG, then the parse tree
/ derivation tree will be as follows:
www.sandipuniversity.edu.in
Department of Computer Engineering & Information Technology, SITRC, Nashik www.sandipfoundation.org
❑ Derivation tree is a graphical representation for the derivation of the

given production rules for a given CFG.
❑ It is the simple way to show how the derivation can be done to obtain
some string from a given set of production rules. The derivation tree is
also called a parse tree.
❑ 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.
❑ A parse tree contains the following properties:
1. The root node is always a node indicating start symbols.

2. The derivation is read from left to right.
3. The leaf node is always terminal nodes.
4. The interior nodes are always the non-terminal nodes.
Example: Construct a derivation tree for the string “aabbabba” for the CFG
given by, S → aB | bA , A → a | aS | bAA, B → b | bS | aBB.
❑ To draw a tree, we will first try to obtain derivation for the string
“aabbabba”.
❑ The derivation or the yield of a parse tree is the final string obtained
by concatenating the labels of the leaves of the tree from left to right,
ignoring the Nulls. However, if all the leaves are Null, derivation is
Null.
❑ There are two different approaches to draw a derivation tree:
1. Top-down Approach
▪ Starts with the starting symbol S.
▪ Goes down to tree leaves using productions.
2. Bottom-up Approach
▪ Starts from tree leaves.
▪ Proceeds upward to the root which is the starting symbol S.
❑ Sentential Form and Partial Derivation Tree: A partial derivation

tree is a sub-tree of a derivation tree/parse tree such that either all of
its children are in the sub-tree or none of them are in the sub-tree.
Example: Let a CFG {N,T,P,S} be N = {S}, T = {a, b}, Starting symbol = S,

P = S → SS | aSb | ε.
❑ One derivation from the above CFG is “abaabb”

S → SS
S → aSbS
S → abS
S → abaSb
S → abaaSbb
S → abaabb
❑ Types of Derivation
❑ Two options to decide which non-terminal to be placed with production
rule.
1. Leftmost Derivation
▪ A leftmost derivation is obtained by applying production to the

leftmost variable in each step.
▪ Leftmost derivation, read the input string from left to right.
2. Rightmost Derivation.
▪ A rightmost derivation is obtained by applying production to
the rightmost variable in each step.
▪ Rightmost derivation, read the input string from right to left.
Example: Let any set of production rules in a CFG be E = E + E | E = E - E |
E = a | b over an alphabet {a, b}, obtain the left & right most derivation
for "a - b + a“.
❑ The derivation for the string "a - b + a" may be:
Leftmost Rightmost
E=E+E E=E-E
E=E-E+E E=E-E+E
E=a-E+E E=E-E+a
E=a-b+E E=E-b+a
E=a-b+a E=a-b+a
Example: Derive the string "aabbabba" for leftmost derivation and rightmost
derivation using a CFG given by, S → aB | bA, S → a | aS | bAA, S → b |
aS | aBB.
❑ The derivation for the string " aabbabba " may be:
String Leftmost Rightmost
S
aB S → aB S → aB
aaBB B → aBB B → aBB
aabB B→b B → bS
aabbS B → bS S → bA
aabbaB S → aB A→ a
aabbabS B → bS B → bS
aabbabbA S → bA S → bA
aabbabba A→ a A→ a
Example: Let any set of production rules in a CFG be X → X+X | X*X |X| a
over an alphabet {a}, obtain the left & right most derivation tree for "a+a*a“.
❑ The leftmost derivation for the string "a+a*a" may be:
X → X+X
X → a+X
X → a + X*X
X → a+a*X
X → a+a*a
❑ The rightmost derivation for the string "a+a*a" may be:

X → X*X
X → X*a
X → X+X*a
X→ X+a*a
X → a+a*a
Generation of Derivation Tree / Parse Tree 14
Leftmost Derivation Rightmost Derivation Leftmost Rightmost

X → X+X X → X*X
X → a+X X → X*a
X → a + X*X X → X+X*a
X → a+a*X X→ X+a*a
X → a+a*a X → a+a*a
Ambiguity in Context-Free Grammar
Derivation 1 Derivation 2
❑ If a context free grammar G has more than one derivation tree for
some string w ∈ L(G), it is called an ambiguous grammar. S → SS S → aSb
❑ A grammar is said to be ambiguous if there exists more than one S → εaSb S → aaSbb
leftmost derivation or more than one rightmost derivation or more S → aaSbb S → aaεbb
than one parse tree for the given input string.
S → aaεbb S → aabb
Example: Check whether the given grammar G is ambiguous or not.
S → aabb
S → aSb | SS, S → ε, for the string “aabb”.
❑ For the string "aabb" the above grammar can generate two parse
trees.
❑ Since there are two parse trees
for a single string "aabb", the
grammar G is an ambiguous.
Ambiguity in Context-Free Grammar
Example: Check whether the grammar G with production rules, X → X+X | Derivation 1 Derivation 2
X*X |X| a, for the string "a+a*a“. X → X+X X → X*X
Derivation / Parse Tree 1 Derivation / Parse Tree 2 X → a+X X → X*a
X → a + X*X X → X+X*a
X → a+a*X X→ X+a*a
X → a+a*a X → a+a*a
❑ Since there are two parse trees for a single string "a+a*a", the grammar
G is an ambiguous.
Ambiguity in Context-Free Grammars
Example: Consider a grammar G with the production rule, E → I, E → E Derivation 1 Derivation 2
+ E, E → E * E, I → ε | 0 | 1 | 2 | ... | 9 , to generate the string “3 * 2 +
5”. E→E*E E→E+E
❑ For the string "3 * 2 + 5", the above grammar can generate two parse E→I*E E→E+I
trees by leftmost derivation: E → I * E+E E → E*E + I
E→I*I+I E→I*I+I
E → 3 * 2+ 5 E → 3 * 2+5
❑ Since there are two parse

trees for a single string
"3 * 2 + 5", the grammar
G is an ambiguous.
Unambiguous Grammar
❑ A grammar can be unambiguous if the grammar does not contain ambiguity that means
if it does not contain more than one leftmost derivation or more than one rightmost
derivation or more than one parse tree for the given input string.
❑ To convert ambiguous grammar to unambiguous grammar, we will apply the following
rules:
1. If the left associative operators (+, -, *, /) are used in the production rule, then apply
left recursion in the production rule. Left recursion means that the leftmost symbol
on the right side is the same as the non-terminal on the left side.
Example: X → Xa
2. If the right associative operates (^) is used in the production rule then apply right
recursion in the production rule. Right recursion means that the rightmost symbol on
the left side is the same as the non-terminal on the right side.
Example: X → aX
Unambiguous Grammar
Example: Consider a grammar G is given as follows: S → AB | aaB, A → a Derivation 1 Derivation 2

| Aa, B → b, show that it an unambiguous grammar for string “aab”. S → AB S → aaB
S → AaB S → aab
❑ Let us derive the string “aab“.
S → aaB
❑ As there are two different parse
S → aab
tree for deriving the same string,
the given grammar is ambiguous.
P = {S → AB
S -> aaB
❑ Unambiguous grammar will be: A→a
S → AB A → Aa
A → Aa | a B → b}
B→b
Unambiguous Grammar
Example: Show that the given grammar is ambiguous for the string “aa”. Derivation 1 Derivation 2
Also, find an equivalent unambiguous grammar for S → ABA, A → aA S → ABA S → ABA
| ε, B → bB | ε. S → aεA S → aABA
❑ Let us derive the string “aa“. S → aεa S → aAεA
❑ As there are two different parse S → aa S → aaAεε
tree for deriving the same string, S → aaεεε
the given grammar is ambiguous. S → aa
❑ Unambiguous grammar will be:

S → ABA S → ABA
S→ AC A → aA
A→ ε
C→ BA B → bB
A→a | ε B → ε.
B→ b | ε
Unambiguous Grammar
Example: Show that the given grammar is ambiguous. Also, find an Derivation 2 Derivation 1
equivalent unambiguous grammar, E → E + E, E → E * E, E → id for E→E*E E→E+E
the string "id + id * id“. E → id * E E → E + id
❑ Let us derive the string "id + id * id“. E → id *E+E E → E*E + id
❑ As there are two different parse E → id*id+id E → id*id+id
tree for deriving the same string,
the given grammar is ambiguous.
❑ Unambiguous grammar will be:

E→E+T
E→T
T→T*F
T→F
F → id
Simplification of CFG
Simplification of CFG’s
❑ Various languages can efficiently be represented by a context-free
grammar. It mainly consist of
❑ All the grammar are not always optimized that means the grammar 1. Removal Useless Symbols
may consist of some extra symbols(non-terminal). Having extra 2. Removal Unit Production
symbols, unnecessary increase the length of grammar.
3. Elimination of ε Production
❑ Simplification of Grammar means reduction of grammar by
removing useless symbols, unit production & elimination of ε.
production.
Simplification of CFF’s
1. Removal of Useless Symbols
It mainly consist of
❑ A symbol can be useless if it does not appear on the right-hand side
of the production rule and does not take part in the derivation of any 1. Removal Useless Symbols
string. That symbol is known as a useless symbol. 2. Removal Unit Production
❑ Similarly, a variable can be useless if it does not take part in the 3. Elimination of ε Production
derivation of any string. That variable is known as a useless variable.
Example: T → aaB | abA | aaT , A → aA , B → ab | b, C → ad
In the above example, the variable 'C' will never occur in the
derivation of any string, so the production C → ad is useless. So
eliminate it, and the other production A → aA is also useless because
there is no way to terminate it. If it never terminates, then it can never
produce a string. Hence this production can never take part in any
derivation.
So Simplified CFG T → aaB | aaT, B → ab | b
2. Removal of Unit Production Simplification of CFF’s
❑ The unit productions are the productions in which one non-terminal It mainly consist of
gives another non-terminal.
1. Removal Useless Symbols
❑ Use the following steps to remove unit production:
2. Removal Unit Production
Step 1: To remove X → Y, add production X → a to the grammar
rule whenever Y → a occurs in the grammar. 3. Elimination of ε Production
Step 2: Now delete X → Y from the grammar.

Step 3: Repeat step 1 and step 2 until all unit productions are
removed.
Example: S → 0A | 1B | C, A → 0S | 00, B → 1 | A, C → 01
S → C is a unit production. But while removing S → C we have to
consider what C gives. So, we can add a rule to S.
S → 0A
S → 1B
S → 01
2. Removal of Unit Production
Example: S → 0A | 1B | C, A → 0S | 00, B → 1 | A, C → 01
S → C is a unit production. But while removing S → C we have to
consider what C gives. So, we can add a rule to S. 2. Removal Unit Production
S → 0A | 1B | 01 3. Elimination of ε Production
Similarly, B → A is also a unit production so we can modify it as
B → 1 | 0S | 00
Thus finally we can write CFG without unit production as
S → 0A | 1B | 01
A → 0S | 00
B → 1 | 0S | 00
❑ The productions of type S → ε called ε Productions. These type of
productions can only be removed from those grammars that do not 1. Removal Useless Symbols
generate ε. 2. Removal Unit Production
❑ Use the following steps to Elimination of ε Production: 3. Elimination of ε Production
Step 1: First find out all null able non-terminal variable which
derives ε.
Step 2: For each production A → a, construct all production A → x,
where x is obtained from a by removing one or more non-terminal
from step 1.
Step 3: Now combine the result of step 2 with the original production
and remove ε productions.
Example: Remove the production from the following CFG by preserving
the meaning of it. S → XYX, X → 0X | ε, Y → 1Y | ε.
the meaning of it. S → XYX, X → 0X | ε, Y → 1Y | ε. 1. Removal Useless Symbols
❑ Now, while removing ε production, we are deleting the rule X → ε 2. Removal Unit Production
and Y → ε. To preserve the meaning of CFG we are actually placing 3. Elimination of ε Production
ε at the right-hand side whenever X and Y have appeared. Then
S → XYX
❑ If the first X at right-hand side is ε. Then
S → YX
❑ Similarly if the last X in R.H.S. = ε. Then
S → XY
❑ If Y = ε then
S → XX
3. Elimination of ε Production Simplification of CFF’s
Example: Remove the production from the following CFG by preserving It mainly consist of
the meaning of it. S → XYX, X → 0X | ε, Y → 1Y | ε.
❑ If Y and X are ε then,
2. Removal Unit Production
S→X
❑ If both X are replaced by ε
S→Y
Now,
S → XYX | XY | YX | XX | X | Y
❑ Now let us consider
X → 0X If Y = ε then
❑ If we place ε at right-hand side for X then,
X→0
X → 0X | 0
the meaning of it. S → XYX, X → 0X | ε, Y → 1Y | ε. 1. Removal Useless Symbols
❑ Similarly 2. Removal Unit Production
Y → 1Y | 1 3. Elimination of ε Production
❑ Collectively we can rewrite the CFG with removed ε production as If

Y and X are ε then,
S → XYX | XY | YX | XX | X | Y
X → 0X | 0
Y → 1Y | 1
Normal Form
Normal Form
❑ CFG always should be in some standard form.
It mainly of two types
❑ There are mainly two normal forms:
1. Chomsky's Normal Form (CNF) 1. Chomsky's Normal Form
2. Greibach Normal Form (GNF) 2. Greibach Normal Form
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:
▪ Start symbol generating ε.
Example: S → ε
▪ A non-terminal generating two non-terminals.
Example: S → AB
▪ A non-terminal generating a terminal.
Example: S → a
Chomsky's Normal Form (CNF)
Normal Form
1. Chomsky's Normal Form (CNF)
Example: G1 = {S → AB, S → c, A → a, B → b}
1. Chomsky's Normal Form
G2 = {S → aA, A → a, B → c}
2. Greibach Normal Form
❑ The production rules of Grammar G1 satisfy the rules specified for
CNF, so the grammar G1 is in CNF.
G1 = { S → AB, S → c
A → a, B → b } ……….. all are in CNF
❑ However, the production rule of Grammar G2 does not satisfy the
rules specified for CNF as S → aZ contains terminal followed by
non-terminal. So the grammar G2 is not in CNF.
G2 = { S → aA, A → a, B → c} ……….. all are not in CNF
1. Chomsky's Normal Form (CNF) Normal Form
❑ Steps for converting CFG into CNF: It mainly of two types
Step 1: Eliminate start symbol from the RHS. If the start symbol T is 1. Chomsky's Normal Form
at the right-hand side of any production, create a new production as:
S1 → S (Where S1 is the new start symbol)
Step 2: In the grammar, remove the null, unit and useless

productions. You can refer to the Simplification of CFG.
Step 3: Eliminate terminals from the RHS of the production if they

exist with other non-terminals or terminals.
Example: Production S → aA can be decomposed as:
S → RA, R → a
Step 4: Eliminate RHS with more than two non-terminals. For
example, S → ASB can be decomposed as:
S → RS, R → AS
1. Chomsky's Normal Form (CNF) Normal Form
Example: Convert the given CFG to CNF. Consider the given grammar It mainly of two types
G1: S → a | aA | B, A → aBB | ε, B → Aa | b.
❑ Step 1: We will create a new production S1 → S, as the start symbol
S appears on the RHS. The grammar will be: 2. Greibach Normal Form
S1 → S
S → a | aA | B
A → aBB | ε
B → Aa | b
❑ Step 2: As grammar G1 contains A → ε null production, its removal
from the grammar yields:
S1 → S
S → a | aA | B
A → aBB
B → Aa | b | a
Normal Form
❑ Now, as grammar G1 contains Unit production S → B, its removal
yield: It mainly of two types
S1 → S 1. Chomsky's Normal Form
S → a | aA | Aa | b 2. Greibach Normal Form
A → aBB
B → Aa | b | a
❑ Also remove the unit production S1 → S, its removal from the

grammar yields:
S0 → a | aA | Aa | b
S → a | aA | Aa | b
A → aBB
B → Aa | b | a
Normal Form
❑ Step 3: In the production rule S0 → aA | Aa, S → aA | Aa, A → aBB
and B → Aa, terminal a exists on RHS with non-terminals. So we It mainly of two types
will replace terminal a with X. 1. Chomsky's Normal Form
S0 → a | XA | AX | b 2. Greibach Normal Form
S → a | XA | AX | b
A → XBB
B → AX | b | a
X→a
❑ Step 4: In the production rule A → XBB, RHS has more than two
symbols, removing it from grammar yield:
S0 → a | XA | AX | b
S → a | XA | AX | b
A → RB, B → AX | b | a
X → a, R → XB
Greibach Normal Form (GNF)
2. Greibach Normal Form (GNF) Normal Form
❑ GNF stands for Greibach normal form. A CFG (Context Free It mainly of two types
Grammar) is in GNF (Greibach Normal Form) if all the
production rules satisfy one of the following conditions: 1. Chomsky's Normal Form
▪ Start symbol generating ε.
Example: S → ε
▪ A non-terminal generating a terminal.
Example: S → a
▪ A non-terminal generating a terminal which is followed by any
number of non-terminals.
Example: S → aASB
2. Greibach Normal Form (GNF) Normal Form
Example: G1 = {S → aAB | aB, A → aA| a, B → bB | b} It mainly of two types
G2 = {S → aAB | aB, A → aA | ε, B → bB | ε} 1. Chomsky's Normal Form
❑ The production rules of Grammar G1 satisfy the rules specified for 2. Greibach Normal Form
GNF, so the grammar G1 is in GNF.
G1 = { S → aAB | aB,
A → aA | a
B → bb | b } ……….. all are 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.
G2 = { S → aAB | aB,
A → aA | ε,
B → bB | ε} ……….. all are not in GNF
Normal Form
2. Greibach Normal Form (GNF)
❑ Steps for converting CFG into GNF: 1. Chomsky's Normal Form
Step 1: Convert the grammar into CNF. 2. Greibach Normal Form
Step 2: If the grammar exists left recursion, eliminate it.
Step 3: In the grammar, convert the given production rule into GNF
form.
Normal Form
2. Greibach Normal Form (GNF)
Example: Convert the given CFG to GNF. Consider the given grammar,
S → XB | AA, A → a | SA, B → b, X → a. 1. Chomsky's Normal Form
❑ As the given grammar G is already in CNF and there is no left 2. Greibach Normal Form
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:
S → XB | AA
A → a | XBA | AAA
B→b
X→a
Normal Form
❑ The production rule S → XB and B → XBA is not in GNF, so we
substitute X → a in the production rule S → XB and B → XBA as: It mainly of two types
S → aB | AA 1. Chomsky's Normal Form
A → a | aBA | AAA 2. Greibach Normal Form
B→b
X→a
❑ Now we will remove left recursion (A → AAA), we get:
S → aB | AA
A → aC | aBAC
C → AAC | ε
B→b
X→a
❑ Now we will remove null production C → ε, we get: Normal Form
S → aB | AA It mainly of two types
A → aC | aBAC | a | aBA 1. Chomsky's Normal Form
C → AAC | AA 2. Greibach Normal Form
B→b
X→a
❑ The production rule S → AA is not in GNF, so we substitute
A → aC | aBAC | a | aBA in production rule S → AA as:
S → aB | aCA | aBACA | aA | aBAA
A → aC | aBAC | a | aBA
C → AAC
C → aCA | aBACA | aA | aBAA
B→b
X→a
Normal Form
❑ The production rule C → AAC is not in GNF, so we substitute A →
aC | aBAC | a | aBA in production rule C → AAC as: It mainly of two types
S → aB | aCA | aBACA | aA | aBAA
A → aC | aBAC | a | aBA
C → aCAC | aBACAC | aAC | aBAAC ….. is in GNF
C → aCA | aBACA | aA | aBAA
B→b
X→a
Chomsky Hierarchy
❑ Chomsky Hierarchy represents the class of languages that are

accepted by the different machine.
❑ The category of language in Chomsky's Hierarchy is as given
below:
1. Type 3 : Regular Grammar
2. Type 2 : Context Free Grammar
3. Type 1 : Context Sensitive Grammar
4. Type 0 : Unrestricted Grammar
Chomsky Hierarchy
1. Type 3 : Regular Grammar

❑ Type 3 Grammar is known as Regular Grammar. Regular languages
are those languages which can be described using regular
expressions.
❑ These languages can be modeled by NFA or DFA.
❑ Type 3 is most restricted form of grammar.
❑ The Type 3 grammar should be Type 2 and Type 1. Type 3 should be

in the form of
V → T*V / T*
Example: A → xy
Chomsky Hierarchy
2. Type 2 : Context Free Grammar

❑ Type 2 Grammar is known as Context Free Grammar. Context free
languages are the languages which can be represented by the
context free grammar (CFG).
❑ Type 2 should be type 1. The production rule is of the form
A→ α
❑ Where A is any single non-terminal and is any combination of
terminals and non-terminals.
Example: A → aBb
A→b
B→a
Chomsky Hierarchy
3. Type 1 : Context Sensitive Grammar

❑ Type 1 grammar is known as Context Sensitive Grammar. The
context sensitive grammar is used to represent context sensitive
language.
❑ The context sensitive grammar follows the following rules:
▪ The context sensitive grammar may have more than one symbol
on the left hand side of their production rules.
▪ The number of symbols on the left-hand side must not exceed
the number of symbols on the right-hand side.
▪ The rule of the form A → ε is not allowed unless A is a start
symbol. It does not occur on the right-hand side of any rule.
▪ The Type 1 grammar should be Type 0. In type 1, Production is
in the form of V → T
❑ Where the count of symbol in V is less than or equal to T.
Example: S → AT, T → xy, A → a

VNW Ce Toc Un 03

Uploaded by

Copyright:

Available Formats

VNW Ce Toc Un 03

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

VNW Ce Toc Un 03

Uploaded by

Copyright:

Available Formats

Program: BE (Computer Engineering & Information Technology)

❑ A derivation tree or parse tree is an ordered rooted tree that

❑ Derivation tree is a graphical representation for the derivation of the

1. The root node is always a node indicating start symbols.

❑ Sentential Form and Partial Derivation Tree: A partial derivation

Example: Let a CFG {N,T,P,S} be N = {S}, T = {a, b}, Starting symbol = S,

❑ One derivation from the above CFG is “abaabb”

▪ A leftmost derivation is obtained by applying production to the

String Leftmost Rightmost

❑ The rightmost derivation for the string "a+a*a" may be:

Leftmost Derivation Rightmost Derivation Leftmost Rightmost

❑ Since there are two parse

Example: Consider a grammar G is given as follows: S → AB | aaB, A → a Derivation 1 Derivation 2

❑ Unambiguous grammar will be:

❑ Unambiguous grammar will be:

Step 2: Now delete X → Y from the grammar.

❑ Collectively we can rewrite the CFG with removed ε production as If

1. Chomsky's Normal Form (CNF)

❑ CNF stands for Chomsky normal form. A CFG (context free

Step 2: In the grammar, remove the null, unit and useless

Step 3: Eliminate terminals from the RHS of the production if they

❑ Also remove the unit production S1 → S, its removal from the

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

❑ The production rule

❑ Chomsky Hierarchy represents the class of languages that are

1. Type 3 : Regular Grammar

❑ These languages can be modeled by NFA or DFA.

❑ Type 3 is most restricted form of grammar.

❑ The Type 3 grammar should be Type 2 and Type 1. Type 3 should be

2. Type 2 : Context Free Grammar

3. Type 1 : Context Sensitive Grammar

You might also like