Normal Forms

for
Context-free Grammars
 Chomsky Normal Form (CNF)

All productions have form:

A  BC and Aa

variable variable terminal

2
 Examples:

S  AS S  AS
S a S  AAS
A  SA A  SA
Ab A  aa
Chomsky Not Chomsky
Normal Form Normal Form

3
Conversion to Chomsky Normal Form

Example: S  ABa
A  aab
B  Ac

Not Chomsky
Normal Form

4
Introduce variables for terminals: Ta , Tb , Tc

S  ABTa
S  ABa A  TaTaTb
A  aab B  ATc
B  Ac Ta  a
Tb  b
Tc  c
5
 Introduce intermediate variable: V1
S  AV1
S  ABTa
V1  BTa
A  TaTaTb
A  TaTaTb
B  ATc
B  ATc
Ta  a
Ta  a
Tb  b
Tb  b
Tc  c
Tc  c
6
 Introduce intermediate variable:V2
S  AV1
S  AV1
V1  BTa
V1  BTa
A  TaV2
A  TaTaTb
V2  TaTb
B  ATc
B  ATc
Ta  a
Ta  a
Tb  b
Tb  b
Tc  c
Tc  c 7
 Final grammar in Chomsky Normal Form:
S  AV1
V1  BTa
A  TaV2
Initial grammar
V2  TaTb
S  ABa B  ATc
A  aab Ta  a
B  Ac Tb  b
Tc  c
8
In general:

From any context-free grammar

not in Chomsky Normal Form

we can obtain:
An equivalent grammar
in Chomsky Normal Form

9
 The Procedure

First remove:

Nullable variables

Unit productions

10
For every symbol a:

Add production Ta  a

In productions: replace a with Ta

New variable: Ta
11
 Replace any production A  C1C2 Cn

with A  C1V1
V1  C2V2

Vn2  Cn1Cn

New intermediate variables: V1, V2 ,  ,Vn2

12
Theorem: For any context-free grammar
there is an equivalent grammar
in Chomsky Normal Form

13
 Observations

• 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

14
 Greibach Normal Form (GNF)

All productions have form:

A  a V1V2 Vk k 0

symbol variables

15
 Examples:

S  cAB
S  abSb
A  aA | bB | b
S  aa
Bb

Greibach Not Greibach

Normal Form Normal Form

16
Conversion to Greibach Normal Form:

S  aTb STb
S  abSb S  aTa
S  aa Ta  a
Tb  b
Greibach
Normal Form
17
Theorem:For any context-free grammar
there is an equivalent grammar
in Greibach Normal Form

18
 Observations

• Greibach normal forms are very good

for parsing

• It is hard to find the Greibach normal

form of any context-free grammar

19
 An Application
of
Chomsky Normal Forms

20
 The CYK Membership Algorithm

Input:

• Grammar G in Chomsky Normal Form

• String w

Output:

find if w L(G )
21
 The Algorithm
Input example:
• Grammar G : S  AB
A  BB
Aa
B  AB
Bb

• String w : aabbb
22
aabbb
a a b b b

aa ab bb bb

aab abb bbb

aabb abbb

aabbb
23
S  AB a a b b b
A  BB A A B B B
Aa aa ab bb bb
B  AB
aab abb bbb
Bb
aabb abbb

aabbb
24
S  AB
A  BB
a a b b b
Aa A A B B B
B  AB
aa ab bb bb
Bb S,B A A
aab abb bbb

aabb abbb

aabbb
25
 a a b b b
S  AB A A B B B
A  BB
Aa
aa ab bb bb
B  AB --- S,B A A
Bb aab abb bbb
S,B A S,B
aabb abbb
A S,B
aabbb
S,B
26
Therefore: aabbb  L(G )

3
Time Complexity: | w|

Observation: The CYK algorithm can be

easily converted to a parser

27
Pushdown Automata
PDAs
 Pushdown Automaton -- PDA
Input String

Stack

States

29
 Initial Stack Symbol

Stack Stack

$ z

bottom
special symbol
30
 The States

Input Pop Push

symbol symbol symbol

a, b  c
q1 q2

31
 a, b  c
q1 q2

input
 a   a 

stack
b top c
h Replace h
e e
$ $
32
 a,  c
q1 q2

input
 a   a 

stack c
b top b
h Push h
e e
$ $
33
 q1 a, b   q2

input
 a   a 

stack
b top
h Pop h
e e
$ $
34
 q1 a ,   q2

input
 a   a 

stack
b top b
h No Change h
e e
$ $
35
 Non-Determinism

q2
a, b  c

q1 q1 , b  c q2

a, b  c  transition
q3

36
 NPDA: Non-Deterministic PDA

Example:

a,  a b,a  

q0 ,  q1
b,a  
q2
 ,$  $
q3
37
 Execution Example: Time 0
Input
a a a b b b
$
Stack

current a,  a b,a  
state
,  b,a    ,$  $
q0 q1 q2 q3
38
 Time 1
Input
a a a b b b
$
Stack

a,  a b,a  

q0 ,  q1 b,a   q2
 ,$  $
q3
39
 Time 2
Input
a a a b b b a
$
Stack

a,  a b,a  

,  b,a    ,$  $
q0 q1 q2 q3
40
 Time 3
Input a
a a a b b b a
$
Stack

a, a b,a 

q0  ,    q1 b, a   q2
,$  $
q3
41
 Time 4
a
Input
a
a a a b b b a
$
Stack

a , a b,a 

q0  ,    q1 b, a   q2  , $  $ q3
42
 Time 5
a
Input
a
a a a b b b a
$
Stack

a, a b,a 

q0 ,q1
b,a 
q2 ,$  $
q3
43
 Time 6
Input a
a a a b b b a
$
Stack

a , a b,a 

, b,a  ,$  $

q3
q0 q1 q2
44
 Time 7
Input
a a a b b b a
$
Stack

a , a
b,a 

, b,a  ,$  $

q0 q1 q2 q3
45
 Time 8
Input
a a a b b b
$
Stack

a , a b,a 
accept
, b,a  ,$  $
q0 q1 q2 q3
46
 A string is accepted if:

• All the input is consumed

• The last state is a final state

We do not care about the stack contents

47
 The input string aaabbb
is accepted by the NPDA:

a , a b,a 

, b,a  ,$  $

q0 q1 q2 q3
48
 In general,
n n
L  {a b : n  0}

is the language accepted by the NPDA:

a , a b,a 

, b,a  ,$  $

q0 q1 q2 q3
49
 Another NPDA example

NPDA M
R
L( M )  {ww }

a ,  a a , a 
b ,  b b , b 

, ,$  $
q0 q1 q2
50
 Execution Example: Time 0

Input
a b b a
$
Stack
a , a a , a 
b ,  b b , b 

, ,$  $ q2
q0 q1
51
 Time 1
Input
a b b a
a
$
Stack
a ,  a a , a 
b ,  b b , b 

, ,$  $
q0 q1 q2
52
 Time 2
Input
b
a b b a
a
$
Stack
a ,  a a , a 
b ,  b b , b 

, ,$  $
q0 q1 q2
53
 Time 3
Input
b
a b b a
a
$
Stack
a ,  a a , a 
b ,  b b , b 

, ,$  $
q0 q1 q2
54
 Time 4
Input
b
a b b a
a
$
Stack
a ,  a a , a 
b ,  b b , b 

, ,$  $
q0 q1 q2
55
 Time 5
Input
a b b a
a
$

a ,  a Stack
a , a 
b ,  b b , b 

, ,$  $ q2
q0 q1
56
 Time 6
Input
a b b a
$

a ,  a a , a  Stack
b ,  b b , b 

accept
, ,$  $
q0 q1 q2
57