ACT CH 3 Context Free Languages

WOLKITE UNIVERSITY
College of Computing & Informatics

Department of Computer Science
Regular Program
Automata and Complexity Theory (CoSc3101)

Chapter Three
Context free languages
By: Sisay T. (MSc.)
outline
3.1. Context free languages
3.2. Sentential forms
3.3. Derivation or parsing
3.3.1. Left most and right most derivations
3.3.2. Derivation tree or parse tree
3.3. Parsing and ambiguity
3.4. Simplification of context free grammar
3.4.1. Methods for transforming grammars
3.4.2 Chomsky Normal Form and Grienbach Normal Form
ACT CH-3: Context Free Languages 2
3.1. Context free languages
• Generated from context free grammar/type-2 grammar
• A grammar G=(V, T, P, S) is said to be a context free if G is of the form
Aα, where α(VT)*.
• The right hand side of a CFG is not restricted and it may be null or
combination of variables and terminals.
• That is why we call it context free.
• 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).

Context free languages ...
• Every regular grammar is context-free, so a regular language is also
a context-free one.
• But, languages such as {anbn}, there are non regular languages. this
language can be generated by a context-free grammar
• Hence, regular languages is a proper subset context-free languages.
• CFG is more powerful than finite automata or RE’s, but still cannot
define all possible languages.
• Context free languages are recognized by push down automata
• Many programming languages have recursive structure that can be
defined by CFGs
Con’t...

Example-4: what is the language generated by the CFG given below
G={(S, A), (a,b), (SaAb, AaAb| ε )}
SaAb
aaAbb
 aaaAbbb
aaabbb
a3b3anbn
• Hence the language generated from G is L= {a nbn |n>=1}

Constructing CFG for the given language
• For each CFL, there is a CFG, and each CFG generates a CFL.
• Example 1: Show that the language having any number of a's over the
set ∑= {a} is context free language.
• Solution:
• If it is possible to construct a CFG to generate this language, then we
say that the language is context free.
• As we know the regular expression for the above language is
• r.e. = a*
• Production rule for the Regular expression is as follows:
• S → aS rule 1
• S → ε rule 2
con’t....
• Now if we want to derive a string "aaaaaa", we can start with start symbols.
• S
• aS
• aaS rule 1
• aaaS rule 1
• aaaaS rule 1
• aaaaaS rule 1
• aaaaaaS rule 1
• aaaaaaε rule 2
• aaaaaa
• The r.e. = a* can generate a set of string {ε, a, aa, aaa,.....}. We can have a null
string because S is a start symbol and rule 2 gives S → ε.
Example 2: Construct a CFG for the regular expression (0+1)*
Solution:
The CFG can be given by, Production rule (P):
• S → 0S | 1S
• S→ε
• The rules are in the combination of 0's and 1's with the start symbol.
Since (0+1)* indicates {ε, 0, 1, 01, 10, 00, 11, ....}. In this set, ε is a string,
so in the rule, we can set the rule S → ε.

Example 3: Construct a CFG for a language L = {wcwR | where w € (a, b)*}.
Solution:
• The string that can be generated for a given language is {aacaa, bcb, abcba,
bacab, abbcbba, ....}
• The grammar could be:
• S → aSa rule 1
• S → bSb rule 2
• S→c rule 3
• Now if we want to derive a string "abbcbba", we can start with start symbols.
• S → aSa
• S → abSba from rule 2
• S → abbSbba from rule 2
• S → abbcbba from rule 3
• Thus any of this kind of string can be derived from the given production rules.

• Example 4: Construct a CFG for the language L = anb2n where n>=1.
Solution:
• The string that can be generated for a given language is {abb, aabbbb,
aaabbbbbb....}.
• The grammar could be:
S → aSbb | abb
• Now if we want to derive a string "aabbbb", we can start with start
symbols.
S → aSbb
S → aabbbb

3.2. Sentential forms

3.3. Derivation or parsing
• Replacement of a variable with the right side of one of its productions
is called as derivation.
• Derivation is a sequence of production rules.
• It is used to get the input string through these production rules.
• We use symbol to denote zero or more steps of a derivation
sequence.

Derivation or parsing ...
• During parsing, we have to take two decisions. These are as follows:
 decide the non-terminal which is to be replaced.
 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:
2. Rightmost Derivation:

Left most derivations
• 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: Production rules:
• E=E+E
• E=E-E
• E=a|b
• Input: a - b + a
• The leftmost derivation is:
E=E+E
E=E-E+E
E=a-E+E
E=a-b+E
E=a-b+a
Right most derivations
• 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: Production rules: The rightmost derivation is:
E=E-E
•E = E + E
E=E-E+E
•E = E - E E=E-E+a
•E = a | b E=E-b+a
E=a-b+a
• Input: a - b + a
Example 2
• Derive the string "abb" for leftmost derivation and rightmost
derivation using a CFG given by,
• S → AB | ε
• A → aB
• B → Sb
• Solution: Leftmost derivation Rightmost derivation:

Exercise
1. Derive the string "aabbabba" for leftmost derivation and rightmost
S → aB | bA
A→ a | aS | bAA
B → b | bS | aBB
2. Derive the string "00101" for leftmost derivation and rightmost
S → A1B
A → 0A | ε
B → 0B | 1B | ε

Derivation Tree/parse tree
• It 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 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:
The root node is always a node indicating start symbols.
The derivation is read from left to right.
The leaf node is always terminal nodes.
The interior nodes are always the non-terminal nodes.
Example 1: show the CFG below in the tree structure
• Production rules: solution
E=E+E
E=E*E
E=a|b|c
• Input
• a*b+c
NB: The tree represents the is left most derivation

Example 2: Draw a derivation tree for the string "bbabb" from the
given CFG
• S → bSb | a | b
Solution: Now, the derivation tree for the string "bbabb" is as follows:
or
 simply reading the leaf nodes, we can obtain the desired string.

Derivation Trees
Consider the same example grammar:
S  AB A  aaA |  B  Bb | 
And a derivation of aab :
S  AB  aaAB  aaABb  aaBb  aab
26
S  AB A  aaA |  B  Bb | 
S  AB
S
A B
yield AB
27
S  AB A  aaA |  B  Bb | 
S  AB  aaAB
S
A B
yield aaAB
a a A
28
S  AB A  aaA |  B  Bb | 
S  AB  aaAB  aaABb
S
A B
a a A B b
yield aaABb
29
S  AB A  aaA |  B  Bb | 
S  AB  aaAB  aaABb  aaBb
S
A B
a a A B b
yield
 aaBb  aaBb
30
S  AB A  aaA |  B  Bb | 
S  AB  aaAB  aaABb  aaBb  aab
Derivation Tree S
(parse tree)
A B
a a A B b
yield
  aab  aab
31
Exercise
1. Construct a derivation tree for the string aabbabba for the CFG
given by,
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
2. Show the derivation tree for string "aabbbb" with the following
grammar.
S → AB | ε
A → aB
B → Sb

3.2. Parsing and ambiguity
• A grammar is said to be ambiguous if there exists more than one
leftmost derivation or more than one rightmost derivation or more
than one parse tree for the given input string.
• If the grammar is not ambiguous, then it is called unambiguous.
• If the grammar has ambiguity, then it is not good for compiler
construction.
• No method can automatically detect and remove the ambiguity, but
we can remove ambiguity by re-writing the whole grammar without
ambiguity.

Example 1:
• Let production rule is given as:

• S -> AB|aaB
• A -> a|Aa
• B -> b
• Let us generate string aab
from the given grammar.
Parse trees for generating
string aab are as follows :
• we are getting more than one parse tree.
• Hence, grammar is ambiguous grammar.
Example 2:
• Let us consider a grammar G with the production rule
1. E → I
2. E → E + E
3. E → E * E
4. E → (E)
5. I → ε | 0 | 1 | 2 | ... | 9
• Solution:
• For the string "3 * 2 + 5",
• The above grammar can
generate two parse trees by
leftmost derivation:
Hence, G is ambiguous
Example 3:
• Let production rule is given as:

1. E -> EE+
2. E -> E(E)
3. E -> id
• Parse tree for id(id)id + is:
• Only one parse tree is possible for id(id)id+, so the given grammar
is unambiguous.

Exercise
• Check the given production is ambiguous or not for the string aabb.
1. S → aSb | SS
2. S → ε

3.4. Simplification of context free grammar
•.

Removal of Useless Symbols
• Theorem (useless productions), Let G be a CFG. Then G' that does not
contain any useless variables or productions such that L(G)=L(G').
• A symbol can be useless if:
It does not appear on the right-hand side of the production rule
It does not take part in the derivation of any string.
• Similarly, a variable can be useless if it does not take part in the derivation
of any string.
• For Example:
• T → aaB | abA | aaT
• A → aA
• B → ab | b
• C → ad
Con’t...
• The variable 'C' will never occur in the derivation of any string and
never reach from the starting variable 'T’, so the production C → ad is
useless. Hence, eliminate it.
• Production A → aA is also useless because there is no way to
terminate and never produce a string.
• To remove this useless production A → aA, we will first find all the variables
which will never lead to a terminal string such as variable 'A'.
• Then we will remove all the productions in which the variable ‘A‘ occurs

Elimination of ε Production
• The productions of type S → ε are called ε productions.
• These type of productions can only be removed from those grammars that do
not generate ε.
• Step 1: First find out all nullable 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.

Nullable Variables
  production : X 
Nullable Variable: Y  
Example: S  aMb
M  aMb
M 
Nullable variable   production 42

Removing   productions
S  aMb S  aMb | ab
Substitute
M  aMb M  M  aMb | ab
M 
After we remove all the  productions

all the nullable variables disappear
43
Example 2:Remove the null productions from the following grammar
S -> ABAC
A -> aA / ϵ
B -> bB / ϵ
C -> c
• Solution: To eliminate A -> ϵ we have to change the productions containing A in the
right side. Those productions are S -> ABAC and A -> aA.
• Replacing each occurrence of A by ϵ, we get four new productions.
• S -> ABC / BAC / BC
• A -> a
• Add these productions to the grammar and eliminate A -> ϵ.
S -> ABAC / ABC / BAC / BC
A -> aA / a
B -> bB / ϵ
C -> c

Con’t...
• To eliminate B -> ϵ we have to change the productions containing B on
the right side. Doing that we generate these new productions:
S -> AAC / AC / C
B -> b
• Add these productions to the grammar and remove the production
B -> ϵ from the grammar.
• The new grammar after removal of ϵ – productions is:
S -> ABAC / ABC / BAC / BC / AAC / AC / C
A -> aA / a
B -> bB / b
C -> c
Removing Unit Productions
• The unit productions are the productions in which one non-terminal
gives another non-terminal.
• Steps to remove unit production
• Step 1: To remove X → Y, add production X → a to the grammar rule
whenever Y → a occurs in the grammar.
• Step 2: Now delete X → Y from the grammar.
• Step 3: Repeat step 1 and step 2 until all unit productions are
removed.

Example
1. S → 0A | 1B | C
2. A → 0S | 00
3. B → 1 | A
4. C → 01
Solution:
• 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.
1.S → 0A | 1B | 01

Con’t...
• Similarly, B → A is also a unit production so we can modify it as
1. B → 1 | 0S | 00
• Thus finally we can write CFG without unit production as
1. S → 0A | 1B | 01
2. A → 0S | 00
3. B → 1 | 0S | 00
4. C → 01

Normal Forms
• It is a standardized or simplified representation of the grammar
that facilitates analysis, parsing, or other operations.
• Two commonly used normal forms for CFGs are Chomsky Normal
Form (CNF) and Greibach Normal Form (GNF).
49
Chomsky Normal Form(CNF)
• A CFG(context free grammar) is in CNF(Chomsky normal form) if all
production rules satisfy one of the following conditions:
1. Start symbol generating ε. For example, A → ε.
2. A non-terminal generating two non-terminals.
 For example, S → AB.
3. A non-terminal generating a terminal. For example, S → a.
• To be in CNF, all the productions must derive either two non-terminals
or a single terminal.
• CNF restricts the number of symbols on the right side of a production
to be two.
• The two symbols must be non-terminals or a single terminal.
Example1
S → AB
A→a
B→b
This context free grammar is in Chomsky normal form.
Rule-01: Reduce the grammar completely by-
 Eliminating ∈ productions
 Eliminating unit productions
 Eliminating useless productions
51
Continued….
Rule-02:
• Replace each production of the form A → B1B2B3….Bn , where n > 2
with A → B1C where C → B2B3….Bn.
• Repeat this step for all the productions having more than two variables
on RHS.
Rule-03:
• Replace each production of the form A → aB with A → XB and X →
a.
• Repeat this step for all the productions having the form A → aB.
52
Example-1: Convert the given grammar to CNF-
S → aAD
A → aB / bAB
B→b
D→d
Solution-
Step-01:
The given grammar is already completely reduced.
Step-02:
The productions already in chomsky normal form are-
B→b ………..(1)
D→d ………..(2)
These productions will remain as they are.
53
The productions not in chomsky normal form are-
S → aAD ………..(3)
A → aB / bAB ………..(4)
We will convert these productions in chomsky normal form.
Step-03:
Replace the terminal symbols a and b by new variables Ca and Cb.
This is done by introducing the following two new productions in the grammar-
Ca → a ………..(5)
Cb → b ………..(6)
Now, the productions (3) and (4) modifies to-
S → CaAD ………..(7)
A → CaB / CbAB ………..(8)
Step-04:
Replace AD and AB by new variables CAD and CAB respectively.
This is done by introducing the following two new productions in the grammar-
CAD → AD ………..(9)
CAB → AB ………..(10)
Con’t....
• Now, the productions (7) and (8) modifies to-
S → CaCAD ………..(11)
A → CaB / CbCAB ………..(12)
Step-05:
• From (1), (2), (5), (6), (9), (10), (11) and (12), the resultant grammar is-
S → CaCAD
A → CaB / CbCAB
B→b
D→d
Ca → a
Cb → b
CAD → AD
CAB → AB
This grammar is in chomsky normal form
Problem-02:
Convert the given grammar to CNF-
S → 1A / 0B
A → 1AA / 0S / 0 Step-03:
B → 0BB / 1S / 1
Solution- Replace the terminal symbols 0 and 1 by
Step-01: new variables C and D.
The given grammar is already completely reduced.
Step-02: This is done by introducing the following two
The productions already in chomsky normal form new productions in the grammar-
are- C→0 ………..(6)
A→0 ………..(1) D→1 ………..(7)
B→1 ………..(2)
These productions will remain as they are. Now, the productions (3), (4) and (5)
The productions not in chomsky normal form are- modifies to-
S → 1A / 0B ………..(3) S → DA / CB ………..(8)
A → 1AA / 0S ………..(4) A → DAA / CS ………..(9)
B → 0BB / 1S ………..(5) B → CBB / DS ………..(10)
We will convert these productions in chomsky normal
form.
56
Step-04:
Out of (8), (9) and (10), the productions already in Chomsky

Normal Form are-
S → DA / CB ………..(11)
A → CS ………..(12) Step-06:
B → DS ………..(13)
These productions will remain as they are. From (1), (2), (6), (7), (11), (12), (13), (16),
(17), (18) and (19), the resultant grammar is-
The productions not in chomsky normal form are-
A → DAA ………..(14) S → DA / CB
B → CBB ………..(15)
We will convert these productions in Chomsky Normal Form. A → CS / DE / 0
Step-05: B → DS / CF / 1
C→0
Replace AA and BB by new variables E and F respectively. D→1
E → AA
This is done by introducing the following two new productions in F → BB
the grammar-
E → AA ………..(16)
F → BB ………..(17)
Now, the productions (14) and (15) modifies to-

A → DE ………..(18)
B → CF ………..(19)
57
Grienbach Normal Form(GNF)
• A CFG is in GNF(Greibach normal form) if all the production rules

satisfy one of the following conditions:
1. A start symbol generating ε. For example, S → ε.
2. A non-terminal generating a terminal. For example, A → a.
3. A non-terminal generating a terminal which is followed by any
number of non-terminals. For example, S → aASB.

Example
• G1 = {S → aAB | aB, A → aA| a, B → bB | b}
• 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
• S → XB | AA
• A → a | SA
• B→b
• 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:
• S → XB | AA
• A → a | XBA | AAA
• B→b
• X→a
Con’t...
• 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:
• S → aB | AA
• A → a | aBA | AAA
• 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
Con’t...
• Now we will remove null production C → ε, we get:
• S → aB | AA
• A → aC | aBAC | a | aBA
• C → AAC | AA
• 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
• C → AAC
• C → aCA | aBACA | aA | aBAA
• B→b
• X→a
Con’t
• The production rule C → AAC is not in GNF, so we substitute
A → aC | aBAC | a | aBA in production rule C → AAC as:
• S → aB | aCA | aBACA | aA | aBAA
• C → aCAC | aBACAC | aAC | aBAAC
• C → aCA | aBACA | aA | aBAA
•B→b
• X→a
• Hence, this is the GNF form for the grammar G.

Properties-
 The context free languages are closed under union.

 The context free languages are closed under concatenation.
 The context free languages are closed under kleen closure.
 The context free languages are not closed under intersection and complement.
 The family of regular language is a proper subset of the family of context free
language.
 Each Context Free Language is accepted by a Pushdown automaton.
65
h r e e
t e r- T
C h a p
do f
En
66

ACT CH 3 Context Free Languages

Uploaded by

Copyright:

Available Formats

ACT CH 3 Context Free Languages

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

ACT CH 3 Context Free Languages

Uploaded by

Copyright:

Available Formats

WOLKITE UNIVERSITY

College of Computing & Informatics

Automata and Complexity Theory (CoSc3101)

• A language L is said to be context-free if and only if there is a context-

ACT CH-3: Context Free Languages 3

ACT CH-3: Context Free Languages 7

ACT CH-3: Context Free Languages 10

ACT CH-3: Context Free Languages 13

ACT CH-3: Context Free Languages 14

ACT CH-3: Context Free Languages 15

ACT CH-3: Context Free Languages 16

ACT CH-3: Context Free Languages 17

ACT CH-3: Context Free Languages 18

ACT CH-3: Context Free Languages 21

ACT CH-3: Context Free Languages 22

• It is a graphical representation for the derivation of the given

NB: The tree represents the is left most derivation

ACT CH-3: Context Free Languages 24

ACT CH-3: Context Free Languages 25

And a derivation of aab :

S  AB  aaAB  aaABb  aaBb  aab

ACT CH-3: Context Free Languages 32

ACT CH-3: Context Free Languages 33

• Let production rule is given as:

• Let production rule is given as:

ACT CH-3: Context Free Languages 36

ACT CH-3: Context Free Languages 37

ACT CH-3: Context Free Languages 38

ACT CH-3: Context Free Languages 40

ACT CH-3: Context Free Languages 41

Nullable variable   production 42

After we remove all the  productions

ACT CH-3: Context Free Languages 44

ACT CH-3: Context Free Languages 46

ACT CH-3: Context Free Languages 47

ACT CH-3: Context Free Languages 48

Out of (8), (9) and (10), the productions already in Chomsky

Now, the productions (14) and (15) modifies to-

• A CFG is in GNF(Greibach normal form) if all the production rules

ACT CH-3: Context Free Languages 58

ACT CH-3: Context Free Languages 59

ACT CH-3: Context Free Languages 60

ACT CH-3: Context Free Languages 64

 The context free languages are closed under union.

You might also like