WOLLO UNIVERSITY

KOMBOLCHA INSTITUTES OF TECHNOLOGY

CONTEXT FREE LANGUAGES AND PUSHDOWN AUTOMATA

By: Belachew N.
Email: nbelay2112@[Link] 1
 Outline
✓ Context free languages
✓ Context Free Grammars
✓ Leftmost and right most derivation
✓ Parsing and ambiguity
✓ Sentential forms
✓ Derivation tree or Parse tree
❑ Definition, Relationship between parse trees and derivations.

✓ Simplification of CFG
✓ Chomsky’s hierarchy of Grammar

2
 Context Free Language(CFL)
✓ In formal language theory, a CFL is a language generated by some CFG.
✓ The set of all CFL is identical to the set of languages accepted by PDA
✓ The language describes a simple kind of nested structure found in
programming languages, indicating that some properties of programming
languages require something beyond regular languages.
✓ In order to cover this and other more complicated features we must enlarge
the family of languages.
✓ This leads us to consider context-free languages and grammars.

3
 …cont’d
✓ E.g. L = {anbn : n ≥ 0}
✓ Context-free languages have applications in compiler design (parsers).
✓ The syntax of programming languages is often given in the form of context-
free grammar, or equivalent Backus-Naur form (BN-form)
✓ BNF
❑ Invented by John Backus to describe ALGOL 58
❑ It is a formal, mathematical way to specify context-free grammars
❑ BNF is a natural notation for describing syntax
❑ BNF is a metalanguage for programming languages.

4
 Context Free Grammars
✓ The productions in a regular grammar are restricted in two ways:
❑ The left side must be a single variable, while
❑ The right side has a special form.
✓ To create grammars that are more powerful, we must relax some
of these restrictions.
✓ By retaining the restriction on the left side, but permitting
anything on the right, we get context-free grammars.

5
 …cont’d
❑A grammar G = (V, T, S, P) is said to be context-free, if all productions in
P have the form A → x, where A ∈ V and x ∈ (V ∪ T)*
❑A language L is said to be context-free if and only if there is a context-free
grammar G such that L= L (G).
❑ The class of context-free languages generalizes the class of regular
languages,
➢ i.e., every regular language is a context-free language but, the reverse of this
is not true

6
 …cont’d
✓ Formally, G = (V, T, P, S) is a Context-Free Grammar (CFG) where:
❑ V - A finite set of variables or non-terminals
❑ T - A finite set of terminals
❑ P - A finite set of productions, each of the form A –> α, where A is in V and α is in (V U T)*,
Note that α may be ε
❑ S - A starting non-terminal (S is in V)

✓ Derivation
❑ Generation of language using specific rules is called derivation.
➢ In derivation of string: replacing the non -terminal by appropriate rule.

7
 …cont’d
✓ Example: for generating a language that generates equal number of a’s and
b’s in the form anbn, the CFG will be defined as
✓ G={(S,A), (a, b), (S –>aAb, A –>aAb|ε)
S=> aAb
=> aaAbb
=> aaaAbbb
=> aaabbb

=>a3b3

8
 …cont’d
✓ Example CFG: ✓ Derivations
✓ G = ({A, B, C, S}, {a, b, c}, P, S)
S=> ABC S=> ABC
✓ P: => BC => aABC
❑ S –> ABC =>C => aaABC
=> ε => aaBC
❑ A –> aA => aabBC
A –> aA | ε
❑ A –> ε => aabC
=> aabcC
❑ B –> bB
B –> bB | ε => aabc
❑ B –> ε
❑ C –> cC
C –> cC | ε ✓ Note that G generates the language a*b*c*
❑ C –> ε

9
 …cont’d
✓ Definition:
❑ Let G = (V, T, P, S) be a context-free grammar. Then the language generated by G, denoted L(G),
is the set:
➢ {w | w is in T* and S=>* w}
❑ Let L be a language. Then L is a context-free language if and only if there exists a context-free
grammar G such that L = L(G).
❑ Let G1 and G2 be context-free grammars. Then G1 and G2 are equivalent if and only if L(G1) =
L(G2).

10
 Leftmost Derivation and Rightmost Derivation
✓ If there are more non-terminal available then which non-terminal has
to replace first; which is based on the two methods are listed below:
❑ Leftmost derivation − A leftmost derivation is obtained by applying production to the
leftmost variable in each step.
❑ Rightmost derivation − A rightmost derivation is obtained by applying production to
the rightmost variable in each step.

11
 …cont’d
✓ Example: Let G be the grammar ✓ First write the production rules separately like
S → aB | bA below

A → a | aS | bAA S → aB rule1
B → b | bS | aBB S → bA rule2
✓ For the string baaabbabba find leftmost, A→a rule3
rightmost derivation and Derivation tree A → aS rule4
A → bAA rule5
B→b rule6
B → bS rule7
B → aBB rule8

12
 …cont’d
Leftmost Derivation Rightmost Derivation
S S
bA r2 bA r2
baS r4 baS r4
baaB r1 baaB r1
baaaBB r8 baaaBB r8
baaabSB r7 baaaBbS r7
baaabbAB r2 baaaBbbA r2
baaabbaB r3 baaaBbba r3
baaabbabS r6 baaabSbba r7
baaabbabbA r1 baaabbAbba r2
baaabbabba r3 baaabbabba r3

13
 Derivation Tree
✓ Derivation tree called parse tree is a graphical representation for the derivation of the given
production rules for the given CFG.
❑ Representation Technique
➢ Root node indicating start symbol
➢ Derivation is read from left to right
➢ Leaf nodes are terminals
➢ The interior nodes are non terminals

✓ If S → x1x2 …… xn is a production rule in a CFG, then the parse tree /

14
 …cont’d
✓ There are two different approaches to draw a derivation tree:
❑ Top-down Approach :
➢ Starts with the starting symbol S
➢ Goes down to tree leaves using productions
❑ Bottom-up Approach :
➢ Starts from tree leaves
➢ Proceeds upward to the root which is the starting symbol S

15
 Derivation or Yield of a Tree
✓ 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.

16
 …cont’d
✓ 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 → aSbS → abS → abaSb → abaaSbb → abaabb

17
 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
❑ If in any CFG the productions are −
➢ S → AB, A → aaA | ε, B → Bb| ε
❑ the partial derivation tree can be

✓ If a partial derivation tree contains the root S, it is called a sentential form. The
above sub-tree is also in sentential form.

18
 Ambiguity in Context-Free Grammars
✓ If a context free grammar G has more than one derivation tree for some
string w ∈ L(G), it is called an ambiguous grammar.
✓ There exist multiple right-most or left-most derivations for some string
generated from that grammar.
✓ Example:
✓ Check whether the grammar G with production rules −
❑ X → X+X | X*X |X| a is ambiguous or not?

✓ Solution
❑ Let’s find out the derivation tree for the string "a+a*a". It has two leftmost derivations.
➢ Derivation 1 − X → X+X → a +X → a+ X*X → a+a*X → a+a*a
➢ Derivation 2 − X → X*X → X+X*X → a+ X*X → a+a*X → a+a*a

19
 …cont’d
✓ Parse tree 1 − ✓ Parse tree 1I −

✓ Since there are two parse trees for a single string "a+a*a", the
grammar G is ambiguous.

20
 Simplification of CFG
✓ All Grammars are not always optimized.
✓ That means grammars are containing some unnecessary symbols(non-
terminals) and this will increase the length of the grammar.
✓ Simplification of grammar means reduction of grammar by removing useless
symbols.
❑ Removal of useless symbols
❑ Elimination of production
❑ Removal of unit production

21
 Removal of Useless Symbols
✓ Remove the useless non-terminals from the production rules.
✓ It will lead to reduce the length of the grammar.
✓ Example 1: remove the useless symbols from the given production rule:
P = {S → A11B | 11A
S → B | 11
A→0
B → BB }
❑ In the above production rule: non-terminals S and A are having some terminal in the rules.
❑ But B is not containing any terminal so it will not terminate at the production so non-terminal B
is useless symbol, so remove the non-terminal B from the production rules.

22
 …cont’d
❑ Remove the rules from the production rule which are containing the non-terminal B in
the rule, so the rule1, rule3 and rule6 are removed from the Production rule, so the
minimize CFG is:
P= { S → 11A | 11
A→0 }
✓ Example 2: Simplify the given CFG
S → AB | CA
B → BC | AB
A→a
C → aB | b

23
 …cont’d
✓ In the above production rule: non-terminals A and C are having some
terminals.
✓ But non-terminal B is not containing any terminal, so it will not terminate
the derivation process.
✓ So remove the rules which are containing the non-terminal B from the
production rule.
✓ S → CA A→a C→b

24
 Elimination of Production Rule
✓ Remove the symbol from the grammar without affecting the meaning of
the grammar.
✓ Thus is not necessary for the grammar.
✓ Example 1: Remove the production from the following CFG
S → XYX
X → 0X |
Y → 1Y |

25
 …cont’d
✓ To remove the production, delete the production rule and to preserve
the meaning of the CFG, placing the value in the other production instead
of the corresponding non-terminal.
✓ Step1: remove the production
✓ Remove the rules X → and Y →

26
 …cont’d
✓ Step2: To preserve the meaning of grammar:
✓ Place the X → to rule 1:
S → XY → XY
S → YX → YX
S→ Y →Y
❑ Place the Y → to rule 1: S → X X → XX
❑ Place the X → and Y → to rule 1: S → X →X
❑ Place the X → to rule 2: X → 0 → 0
❑ Place the Y → to rule 4: Y → 1 → 1
❑ Collectively can write the CFG:
S → XY | YX | XX | X |Y
X→0
Y→1

27
 Removing the Unit production
✓ Unit productions are the productions in which one non-terminal gives another non-terminal only without
terminal.
✓ X → Y and Y → Z
Then you can minimize the rule like X → Z
Example 1: Remove the unit productions from given CFG
S → 0A | 1B | C
A → 0S | 00
B→1|A
C → 01
In the above production rule: S → C is unit production so in rule3 you can replace the C value by rule8.
S → 0A | 1B | 01
A → 0S | 00
B→1|A
C → 01 useless productions

28
 …cont’d
✓ Example 2: Optimize the given CFG by reducing the grammar
S → A | 0C1
A → B | 01 | 10
C → | CD
✓ B and D are useless symbols because B and D is not available
S → A is a unit production
C→ - production
✓ The below After removal of useless symbol, unit production and production
S → 01 | 10

29
 Normal Forms
✓ Normalization is performed in order to standardize the grammar.
✓ By reducing the grammar, the grammar gets minimized but does not gets
standardized.
✓ This is because the RHS of productions have no specific format.
✓ In order to standardize the grammar, normalization is performed using
normal forms.
✓ The most frequently used normal forms are-
1. Chomsky’s Normal Form (CNF)
2. Greibach Normal Form (GNF)

30
 Chomsky’s 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.
❑ Start symbol generating ε. For example, A → ε.

31
 …cont’d
✓ Procedure for converting to CNF:
❑ Simplify the CFG
❑ Eliminate non-terminal, if more than two non-terminal presented in the production and make new
rule
▪Ex: S → ABA
▪ In CNF form: P → BA rule 1
S → AP rule 2
➢ See the rule 1 and 2, only two non-terminals only available in right of the production.

❑ Eliminate the terminal, if more than one terminal is presented in the production and make new rule
▪Ex: S → aa
▪In CNF form: P1 → a rule1
P2 → a rule2
 Now see the rule1 and 2 are containing only one terminal.
S → P1P2 rule3 Also rule3 is containing two non-terminals only

32
 …cont’d
✓ Example 1: Convert the given CFG to CNF
S → aSa | bSb | a | b
Write the rules separately S → aSa rule1
S → bSb rule2
S → a rule3
S → b rule4
✓ Start with adding new symbol for the terminals
A→a new rule1
B→b new rule2
✓ Apply new rule1 in rule1
S → ASA in this rule three non-terminal available so eliminate the non-terminals
S → AP1 new rule3
P1 → SA new rule4

33
 …cont’d
✓ Apply new rule2 in rule2
❑ S → BSB in this rule three non-terminal available so eliminate the non-terminals
❑ S → BP2 new rule5
❑ P2 → SB new rule6

✓ Now consider the rule3 and rule4, these two rules are already in CNF
format so no need to change it.

34
 …cont’d
✓ Finally the CFG in CNF
A→a new rule1
B→b new rule2
S → AP1 new rule3
P1 → SA new rule4
S → BP2 new rule5
P2 → SB new rule6
S→a new rule7
S→b new rule8

35
 …cont’d
Example 2: Reduce the following grammar to chomsky normal form.
S → a | AAB
A → ab | aB |
B → aba |
First simplify the given grammar by removal of unit production, useless
symbol and production. After simplify the above CFG you will get the
simplified CFG like the below:

S → a | AB | AA | B
A → ab | aB | a
B → aba

36
 …cont’d
In the simplified CFG, rule1, rule2, rule3 and rule7 are already in CNF.
Rule4 S → B can be
B → aba
Let P1 → a is in CNF newrule1
P2 → b is in CNF newrule2
so now B → P1P2P1
P3 → P2P1 is in CNF newrule3
so B →P1P3 is in CNF newrule4
So S → P1P3 in CNF newrule5
Rule5 A → ab apply the newrule1 and 2
So A → P1P2 is in CNF newrule6
Rule6 A → aB apply the newrule1
So A → P1B is in CNF newrule7

37
 …cont’d
Final the CFG in CNF
P1 → a
P2 → b
P3 → P2P1
B →P1P3
S → P1P3
A → P1P2
A → P1B
S → a | AB | AA
A→a

38
 Greibach Normal Form (GNF)
✓ A CFG(context free grammar) is in GNF(Greibach normal form) if all the
production rules satisfy one of the following conditions:
❑ A start symbol generating ε. For example, S → ε.
❑ 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.

✓Only one terminal and any number of non-terminals in the right of

39
 …cont’d
Example 1: Convert the grammar CFG to GNF Now consider rule2: S → aa
S → abSb rule1 if we create another NT to define terminal a.
S → aa rule2 A→a newrule3
Consider rule1: S → abSb Hence S → aA newrule4
if we create another NT to define terminal b. So the GNF will be:
B→b newrule1 S → aBSB | aA
Hence S → aBSB newrule2 A→a
B→b

40
 Chomsky’s hierarchy of Grammar
The Chomsky hierarchy
Type-0 Unrestricted Grammar
Type-1 Context Free Grammar
Type-2 Context Sensitive Grammar
Type-3 Regular Grammar

41
 …cont’d
✓ Type-0 Unrestricted Grammar:
❑ It includes all formal grammars. It generate exactly all languages that can recognized by Turing machine.
These languages are known as Recursively Enumerable Language
✓ Type-1 Context Sensitive Grammar:
❑ Generate the context-sensitive languages. The languages described by these grammars are exactly all
languages that can be recognized by a linear bounded automata
✓ Type-2 Context Free Grammar:
❑ Generate the context-free languages. These are defined by rules of the form with a non-terminal and a
string of terminals and/or non-terminals. These languages are exactly all languages that can be
recognized by a non-deterministic pushdown automaton.
✓ Type-3 Regular Grammar:
❑ Generate the regular languages. Such a grammar restricts its rules to a single non-terminal on the left-
hand side and a right-hand side consisting of a single terminal, possibly followed by a single non-
terminal (right regular).

42
 End of Ch.3
Questions, Ambiguities, Doubts, … ???

43