Intro to Theory of Computation
Trist1111
Ch6CNFv2.pptx1
Normal Forms for Context-free Grammars
2
First remove all
Step 1: Remove Nullable Variables
Step 2: Remove Unit-Productions
Step 3: Remove Useless Variables
3
Chomsky Normal Form
Each productions has form:
variable
variable
or
terminal
4
Examples:
Not Chomsky
Normal Form
Chomsky
Normal Form
Why is CNF easier to parse?
5
6
7
Convertion to Chomsky Normal Form
Example:
Not Chomsky
Normal Form
8
Introduce variables for terminals:
9
Introduce intermediate variable:
10
Introduce intermediate variable:
11
Final grammar in Chomsky Normal Form:
Initial grammar
12
From any context-free grammar
(which doesn’t produce )
not in Chomsky Normal Form
we can obtain:
An equivalent grammar
in Chomsky Normal Form
In general:
13
The Procedure
First remove:
Useless productions & variables
Nullable variables
Unit productions
14
Then, for every symbol :
In productions: replace with
Add production
New variable:
15
Replace any production
with
New intermediate variables:
16
Theorem:
For any context-free grammar
(which doesn’t produce )
there is an equivalent grammar
in Chomsky Normal Form
17
Observations
Chomsky normal forms are good
for parsing and proving theorems
It is very easy to find the Chomsky normal
form for any context-free grammar
E → T | E + T
T → F | T * F
F → I | (E)
I → a | b | Ia | Ib | I0 | I1
Terminals = {*, +, (, ), a, b, 0, 1}
Example
Terminals = {*, +, (, ), a, b, 0, 1}
Example
E → E + T | T * F | (E ) | a | b | la | lb | l0 | l1
T → T * F | (E) | a | b | Ia | Ib | I0 | I1
F → (E) | a | b | Ia | Ib | I0 | I1
I → a | b | Ia | Ib | I0 | I1
Terminals = {*, +, (, ), a, b, 0, 1}
Example
E → EPT | TMF | LER | a | b | lA | lB | lZ | lO
T → TMF | LER | a | b | IA | IB | IZ | IO
F → LER | a | b | IA | IB | IZ | IO
I → a | b | IA | IB | IZ | IO
A → a B → b Z → 0 O → 1
P → + M → * L → ( R → )
Terminals = {*, +, (, ), a, b, 0, 1}
Example
E → EPT | TMF | LER | a | b | lA | lB | lZ | lO
T → TMF | LER | a | b | IA | IB | IZ | IO
F → LER | a | b | IA | IB | IZ | IO
I → a | b | IA | IB | IZ | IO
A → a B → b Z → 0 O → 1
P → + M → * L → ( R → )
C1 → PT
C2 → MF
C3 → ER
Terminals = {*, +, (, ), a, b, 0, 1}
Example
E → E C1 | T C2 | L C3 | a | b | lA | lB | lZ | lO
T → T C2 | L C3 | a | b | IA | IB | IZ | IO
F → L C3 | a | b | IA | IB | IZ | IO
I → a | b | IA | IB | IZ | IO
C1 → PT
C2 → MF
C3 → ER
A → a B → b Z → 0 O → 1
P → + M → * L → ( R → )
Parsing Algorithms
Top-down vs bottom-up
Type
Naïve – exhaustive search
Backtracking – discard partial solutions
Dynamic Programming – save partial solutions in a table
Example:
CYK Algorithm – bottom-up, dynamic programming, grammar must be in CNF
The CYK Algorithm
The membership problem:
Problem:
Given a context-free grammar G and a string w
G = (V, T ,P , S) where
V finite set of variables
T (the alphabet) finite set of terminal symbols
P finite set of rules
S start symbol (distinguished element of V)
V and T are assumed to be disjoint
Question: Is w in L(G)?
24
BC
A
®
a
A
®
b
A
SA
A
a
S
AS
S
®
®
®
®
aa
A
SA
A
AAS
S
AS
S
®
®
®
®
Ac
B
aab
A
ABa
S
®
®
®
Ac
B
aab
A
ABa
S
®
®
®
c
T
b
T
a
T
AT
B
T
T
T
A
ABT
S
c
b
a
c
b
a
a
a
®
®
®
®
®
®
c
b
a
T
T
T
,
,
c
T
b
T
a
T
AT
B
T
T
T
A
ABT
S
c
b
a
c
b
a
a
a
®
®
®
®
®
®
c
T
b
T
a
T
AT
B
T
T
T
A
BT
V
AV
S
c
b
a
c
b
a
a
a
®
®
®
®
®
®
®
1
1
1
V
c
T
b
T
a
T
AT
B
T
T
V
V
T
A
BT
V
AV
S
c
b
a
c
b
a
a
a
®
®
®
®
®
®
®
®
2
2
1
1
2
V
c
T
b
T
a
T
AT
B
T
T
V
V
T
A
BT
V
AV
S
c
b
a
c
b
a
a
a
®
®
®
®
®
®
®
®
2
2
1
1
Ac
B
aab
A
ABa
S
®
®
®
l
a
a
a
T
a
T
a
®
n
C
C
C
A
L
2
1
®
n
n
n
C
C
V
V
C
V
V
C
A
1
2
2
2
1
1
1
-
-
®
®
®
K
2
2
1
,
,
,
-
n
V
V
V
K
l
