S. J. P. N.
TRUST’S
HIRASUGAR INSTITUTE OF TECHNOLOGY, NIDASOSHI
Accredited at 'A+' Grade by NAAC
Programmes Accredited by NBA: CSE, ECE
Department of Computer Science & Engineering
.IN
Course: Theory of Computation(BCS503)
C
Module 4: Normal Forms for Context
N
SY
Free Grammar
U
VT
Prof. A. A. Daptardar
Asst. Prof. , Dept. of Computer Science &
Engg.,
1
Hirasugar Institute of Technology, Nidasoshi
Module-4
Content to be covered:
.IN
• Normal Forms for Context-Free
C
Grammars, The Pumping Lemma for
N
Context-Free Languages, Closure
SY
Properties of Context-Free Languages.
U
• TEXT BOOK: Sections 7.1, 7.2, 7.3
VT
2
.IN
NORMAL FORMS FOR
CONTEXT FREE GRAMMARS
C
N
SY
Eliminating Useless Symbols
U
Computing the Generating and Reachable Symbols
VT
Eliminating €-Productions
Eliminating Unit Productions
Chomsky Normal Form
3
Introduction
• The goal of this section is to show that
.IN
every CFL (without €) is generated by a
C
CFG in which all productions are of the
N
form A BC or A a, where A, B, and
SY
Care variables, and a is a terminal. This
U
form is called Chomsky Normal Form.
VT
• To get there, we need to make a number
of preliminary simplifications, which are
themselves useful in various ways:
4
• 1. We must eliminate useless symbols,
those variables or terminals that do not
appear in any derivation of a terminal
.IN
string from the start symbol.
C
• 2. We must eliminate €-productions, those
N
of the form A € for some variable A.
SY
• 3. We must eliminate unit productions,
U
those of the form A B for variables
VT
5
7.1.1 Eliminating Useless Symbols
.IN
C
N
SY
U
VT
6
Algorithm
• Stage 1 : Obtain the set of variables and
productions which derive only string of
.IN
terminals.
C
• The algorithm to obtain a set of variables :
N
• Step 1: ( Initialize old_ variables denoted by ov
to ᴓ)
SY
ov = ᴓ
U
VT
• Step 2: Take all productions of the form A x where x ϵ
T+ i.e if the RHS of the production contains only string of
terminals consider those productions and corresponding
non terminals on the LHS are added to new_variables
denoted by nv.
7
nv = {A | A x and x ϵ T+ }
• Step 3: Compare ov and nv: As long as
the elements in ov and nv are not equal,
repeat the following statements. Otherwise
.IN
go to step 4.
• a. [copy new variables to old variables]
C
N
ov = nv
SY
• b. add all the elements in ov to nv. Also
U
add the variables which derive a string
VT
consisting of terminals and non-terminals
which are in ov i.e.
nv = ov U { A | A y and y ϵ (ov U T)*}
8
• Step 4: After completion of step 3, nv(or
ov) contains all those non-terminals from
which only the string of terminals are
.IN
derived and add those variables to V1 i.e
V 1 = ov
C
N
• Step 5 : [Terminate the algorithm]
SY
return V1
U
VT
9
• Stage 2: Obtain the set of variables and
terminals which are reachable from the start
symbol. The productions which are not used are
useless. This can be obtained as shown below:
.IN
• Given a CFG G1 = (V1,T 1,P 1,S), we can find an
C
equivalent grammar G1=(V1,T 1,P 1,S) such that
N
for each X in (V1 U T1) there exists some α such
that
SY
U
VT
• Where X is a symbol in α i.e X is a variable, X ϵ
V 1 and if X is a terminal X ϵ T1. Each symbol X in
(V1 U T1) is reachable from the start symbol S.
10
• The algorithm for this is shown below:
V 1 = {S}
For each A in V1
.IN
If A α then
C
Add the variables in α to V1
N
Add the terminals in α to T1
End if SY
U
End for
VT
• Using this algorithm all those symbols (
whether variables or terminals) that are
not reachable from the start symbol are
eliminated. 11
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
.IN
ELIMINATING
C
N
€-PRODUCTIONS
SY
U
VT
15
Introduction
• A production of the form A ϵ is
.IN
undesirable in a CFG, unless an empty
C
string is derived from the start symbol.
N
Suppose, the language generated from a
SY
grammar G does not derive any empty
U
string and the grammar consists of ϵ –
VT
productions. Such ϵ–productions can be
removed.
16
Definition
• Let G = ( V,T,P,S) be a CFG. A production
.IN
in P of the form
C
A ϵ
N
is called an ϵ–production or NULL
production. SY
U
• After applying the production the variable
VT
A is erased. For each A in V, if there is a
derivation of the form
17
• Then A is a nullable variable.
• A nullable variable is defined as follows:
– 1. If A ϵ is a production in P, then A is a
nullable variable.
.IN
– 2. If A B1B2 ….Bn is a production in P, and
if B1,B2,……Bn are nullable variables, then A
C
is also nullable variable.
N
– 3. The variables for which there are
SY
productions of the form shown in step 1 and
U
step 2 are nullable variables.
VT
18
VT
U
SY
N
C
.IN
19
VT
U
SY
N
C
.IN
20
VT
U
SY
N
C
.IN
21
VT
U
SY
N
C
.IN
22
VT
U
SY
N
C
.IN
23
VT
U
SY
N
C
.IN
.IN
ELIMINATING
C
N
UNIT PRODUCTIONS
SY
U
VT
25
Unit productions
.IN
C
N
SY
U
VT
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
.IN
CNF-
C
N
CHOMSKY NORMAL FORM
SY
U
VT
31
VT
U
SY
N
C
.IN
CNF Definition:
.IN
C
N
SY
U
VT
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
.IN
Computing the Generating
C
and Reachable Symbols
N
SY
U
VT
40
Computing the Generating
Symbols
.IN
C
N
SY
U
VT
41
.IN
• By the basis, a and b are generating. For the
C
induction, we can use the production A b to
N
conclude that A is generating, and we can use
SY
the production S a to conclude that S is
generating.
U
• At that point, the induction is finished.
VT
• We cannot use the production S AB, because
B has not been established to be generating.
• Thus, the set of generating symbols is { a, b, A,
S}. 42
Computing Reachable Symbols
• Let us consider the inductive algorithm
.IN
whereby we find the set of reachable
symbols for the grammar G = (V, T, P, S).
C
N
• BASIS: S is surely reachable.
• INDUCTION: SY Suppose we have
U
discovered that some variable A is
VT
reachable. Then for all productions with A
in the head, all the symbols of the bodies
of those productions are also reachable.
43
.IN
C
• By the basis, S is reachable. Since S has
N
production bodies AB and a, we conclude
SY
that A, B, and a are reachable. B has no
productions, but A has A b. We
U
VT
therefore conclude that b is reachable.
Now, no more symbols can be added to
the reachable set, which is {S,A,B,a,b}.
44
.IN
THE PUMPING LEMMA FOR
CONTEXT FREE LANGUAGES
C
N
SY
The size of the parse tree
U
Statement of the Pumping Lemma
VT
Applications of the Pumping Lemma
45
Introduction
• Now, we shall develop a tool for showing that
.IN
certain languages are not contextfree.
C
• The theorem, called the "pumping lemma for
N
context-free languages," says that in any
SY
sufficiently long string in a CFL, it is possible to
find at most two short, nearby substrings, that
U
VT
we can "pump" in tandem.
• That is, we may repeat both of the strings i
times, for any integer i, and the resulting string
will still be in the language.
46
The Size of the Parse Trees
• Our first step in deriving a pumping lemma
.IN
for CFVs is to examine the shape and size
C
of parse trees. One of the uses of CNF is
N
to turn parse trees into binary trees. These
SY
trees have some convenient properties,
U
one of which we exploit here.
VT
47
VT
U
SY
N
C
.IN
48
The Statement of the Pumping
Lemma
.IN
C
N
SY
U
VT
49
Applications of Pumping Lemma
.IN
C
N
SY
U
VT
50
VT
U
SY
N
C
.IN
51
VT
U
SY
N
C
.IN
52
VT
U
SY
N
C
.IN
53
VT
U
SY
N
C
.IN
54
VT
U
SY
N
C
.IN
55
VT
U
SY
N
C
.IN
56
VT
U
SY
N
C
.IN
57
VT
U
SY
N
C
.IN
58
VT
U
SY
N
C
.IN
59
VT
U
SY
N
C
.IN
60
VT
U
SY
N
C
.IN
61
VT
U
SY
N
C
.IN
62
VT
U
SY
N
C
.IN
63