Chomsky Normal Form
All productions have form:
Normal Forms
for
Context-free Grammars
A BC
variable
Aa
and
variable
terminal
Examples:
Convertion to Chomsky Normal Form
S AS
S AS
S a
A SA
S AAS
A SA
Ab
A aa
Chomsky
Normal Form
S ABa
A aab
B Ac
Example:
Not Chomsky
Normal Form
Not Chomsky
Normal Form
3
Introduce variables for terminals:
Introduce intermediate variable:
Ta , Tb , Tc
S ABTa
S ABTa
S ABa
A aab
B Ac
A TaTaTb
A TaTaTb
B ATc
B ATc
Ta a
Ta a
Tb b
Tb b
Tc c
Tc c
5
V1
S AV1
V1 BTa
A TaTaTb
B ATc
Ta a
Tb b
Tc c
6
1
PDF created with pdfFactory Pro trial version www.pdffactory.com
Introduce intermediate variable:
Final grammar in Chomsky Normal Form:
V2
S AV1
S AV1
S AV1
V1 BTa
V1 BTa
V1 BTa
A TaV2
A TaTaTb
V2 TaTb
B ATc
Ta a
Tb b
Tb b
Tc c
Tc c
V2 TaTb
S ABa
A aab
B Ac
B ATc
Ta a
A TaV2
Initial grammar
B ATc
Ta a
Tb b
Tc c
The Procedure
In general:
From any context-free grammar
not in Chomsky Normal Form
First remove:
Nullable variables
we can obtain:
An equivalent grammar
in Chomsky Normal Form
Unit productions
For every symbol
10
Replace any production
a:
with
Ta a
Add production
A C1C2 Cn
A C1V1
V1 C2V2
In productions: replace
New variable:
with
Vn 2 Cn 1Cn
Ta
Ta
11
New intermediate variables:
V1 , V2 , ,Vn 2
12
2
PDF created with pdfFactory Pro trial version www.pdffactory.com
Observations
Theorem:
For any context-free grammar
there is an equivalent grammar
in Chomsky Normal Form
Chomsky normal forms are good
for parsing and proving theorems
It is very easy to find the Chomsky normal
form of any context-free grammar
13
Greinbach Normal Form
Examples:
S cAB
A aA | bB | b
Bb
All productions have form:
A a V1V2 Vk
symbol
14
k0
Greinbach
Normal Form
variables
S abSb
S aa
Not Greinbach
Normal Form
15
Conversion to Greinbach Normal Form:
S abSb
S aa
16
Theorem:
S aTb STb
For any context-free grammar
there is an equivalent grammar
in Greinbach Normal Form
S aTa
Ta a
Tb b
Greinbach
Normal Form
17
18
3
PDF created with pdfFactory Pro trial version www.pdffactory.com
Observations
Greinbach normal forms are very good
for parsing
An Application
of
Chomsky Normal Forms
It is hard to find the Greinbach normal
form of any context-free grammar
19
20
The Algorithm
The CYK Membership Algorithm
Input example:
Input:
Grammar
String
Grammar
G in Chomsky Normal Form
G : S AB
A BB
Aa
B AB
Bb
Output:
find if
w L(G )
String
w : aabbb
21
S AB
A BB
aabbb
a
aa
ab
bb
bb
aab
abb
b bb
aabb
abbb
22
A a
B AB
Bb
aabb b
23
a
A
a
A
b
B
b
B
aa
ab
bb
bb
aab
abb
bbb
aabb
abbb
aabbb
b
B
24
4
PDF created with pdfFactory Pro trial version www.pdffactory.com
S AB
A BB
S AB
A a
B AB
Bb
a
A
a
A
b
B
b
B
aa
aab
ab
S,B
abb
bb
A
bbb
bb
A
aabb
abbb
b
B
aabbb
Therefore:
Aa
B AB
B b
a
A
a
A
b
B
b
B
aa
bb
A
bbb
S,B
bb
A
aab
S,B
ab
S,B
abb
A
aabb
A
abbb
S,B
aabbb
S,B
25
b
B
26
aabbb L (G )
Time Complexity:
Observation:
A BB
Pushdown Automata
PDAs
| w |3
The CYK algorithm can be
easily converted to a parser
27
28
Pushdown Automaton -- PDA
Initial Stack Symbol
Input String
Stack
Stack
Stack
States
bottom
special symbol
29
30
5
PDF created with pdfFactory Pro trial version www.pdffactory.com
The States
q1
Pop
symbol
Input
symbol
Push
symbol
a, b c
a, c
stack
q2
top
b
h
e
$
31
q1
q2
input
q1
a, b c
q2
q1
input
c
h
e
$
Replace
a, b
32
q2
input
stack
top
b
h
e
$
a,
b
h
e
$
33
top
No Change
top
Pop
h
e
$
34
b
h
e
$
q2
q1
stack
b
h
e
$
Non-Determinism
a, b c
q2
input
stack
c
b
h
e
$
Push
q1
q1
a, b c
35
q3
, b c
q2
transition
These are allowed transitions in
a Non-deterministic PDA (NPDA)
36
6
PDF created with pdfFactory Pro trial version www.pdffactory.com
Execution Example: Time 0
NPDA: Non-Deterministic PDA
Input
Example:
b b
$
Stack
a, a
b, a
a, a
current
state
b, a
q0 , q1 b, a q2 , $ $ q3
q0 , q1 b, a q2 , $ $ q3
37
38
Time 1
Time 2
Input
Input
b b
a
$
$
Stack
a, a
Stack
b, a
a, a
b, a
q0 , q1 b, a q2 , $ $ q3
q0 , q1 b, a q2 , $ $ q3
39
40
Time 3
Input
Time 4
Input
a
a
$
b b
Stack
a, a
a
a
a
$
Stack
b, a
a, a
b, a
q0 , q1 b, a q2 , $ $ q3
q0 , q1 b, a q2 , $ $ q3
41
42
7
PDF created with pdfFactory Pro trial version www.pdffactory.com
Time 5
Input
Time 6
a
a
a
$
Input
a
a
$
Stack
Stack
a, a
b, a
a, a
b, a
q0 , q1 b, a q2 , $ $ q3
q0 , q1 b, a q2 , $ $ q3
43
44
Time 7
Time 8
Input
Input
a
$
b
$
Stack
a, a
Stack
b, a
a, a
b, a
accept
q0 , q1 b, a q2 , $ $ q3
q0 , q1 b, a q2 , $ $ q3
45
46
A string is accepted if there is
a computation such that:
The input string aaabbb
is accepted by the NPDA:
All the input is consumed
The last state is a final state
a, a
At the end of the computation,
we do not care about the stack contents
b, a
q0 , q1 b, a q2 , $ $ q3
47
48
8
PDF created with pdfFactory Pro trial version www.pdffactory.com
In general,
Another NPDA example
L = {a nb n : n 0}
NPDA
is the language accepted by the NPDA:
a, a
L ( M ) = {ww R }
b, a
q0 , q1 b, a q2 , $ $ q3
49
Execution Example:
a, a
a, a
b, b
b, b
q0
Time 0
q1
, $ $
Input
a b
a b
a
$
$
a, a
a, a
b, b
b, b
,
q1
, $ $
Stack
a, a
a, a
b, b
b, b
q2
51
q0
Time 2
q1
, $ $
Stack
q2
52
Time 3
Input
Input
a b
b
a
$
a, a
b, b
q0
50
Time 1
Input
q0
q2
a, a
b, b
q1
, $ $
a b
Stack
Guess the middle
of string
a, a
b, b
q2
53
q0
a, a
b, b
q1
, $ $
b
a
$
Stack
q2
54
9
PDF created with pdfFactory Pro trial version www.pdffactory.com
Time 4
Time 5
Input
Input
a b
b
a
$
a, a
a, a
b, b
b, b
q0
q1
, $ $
a b
Stack
q2
55
a, a
a, a
b, b
b, b
q0
Rejection Example:
Time 6
Input
a
$
q1 , $ $
Stack
q2
56
Time 0
Input
a b
a b
$
a, a
a, a
b, b
b, b
Stack
a, a
a, a
b, b
b, b
Stack
accept
q0
q1
, $ $
q2
57
q0
Time 1
, $ $
q2
58
Time 2
Input
Input
a b
a, a
b, b
q0
q1
a b
a
$
a, a
b, b
q1
, $ $
Stack
a, a
b, b
q2
59
q0
b
a
$
a, a
b, b
q1
, $ $
Stack
q2
60
10
PDF created with pdfFactory Pro trial version www.pdffactory.com
Time 3
Time 4
Input
Input
a b
Guess the middle
of string
a, a
a, a
b, b
b, b
q0
, $ $
a b
Stack
q2
61
a b
a, a
Input is not
consumed
a, a
b, b
b, b
,
q1 , $ $
a, a
a, a
b, b
b, b
q0
Input
, $ $
q2
62
Stack
a, a
a, a
b, b
b, b
63
q0
Time 1
q1
, $ $
Stack
q2
64
Time 2
Input
Input
a b
a, a
b, b
q0
q1
Stack
Time 0
a b
a
$
q2
b
a
$
Another computation on same string:
Time 5
There is no possible transition.
Input
q0
q1
b
a
$
a b
a
$
a, a
b, b
q1
, $ $
Stack
a, a
b, b
q2
65
q0
b
a
$
a, a
b, b
q1
, $ $
Stack
q2
66
11
PDF created with pdfFactory Pro trial version www.pdffactory.com
Time 3
Time 4
Input
a b
a, a
a, a
b, b
b, b
q0
q1
, $ $
Time 5
Input
a b
a, a
b, b
q0
No final state
is reached
a, a
b, b
q1
, $ $
a b
Stack
q2
67
a, a
a, a
b, b
b, b
q0
b
b
b
a
$
q1
, $ $
Stack
q2
68
There is no computation
that accepts string abbb
abbb L(M )
Stack
a, a
b, b
q2
b
b
b
a
$
Input
b
b
a
$
69
q0
a, a
b, b
q1
, $ $
q2
70
12
PDF created with pdfFactory Pro trial version www.pdffactory.com
