```Context-Free Grammars
– Chomsky Normal Form
Lecture 16
Section 2.1
Wed, Sep 26, 2007
Chomsky Normal Form
• A context-free grammar is in
Chomsky Normal Form (CNF) if
each rule is of the form
• A  BC, or
• A  a,
where B and C are not S.
• Furthermore, the rule S   is
allowed.
Chomsky Normal Form
• Theorem: Every context-free
language is generated by a
grammar in CNF.
Chomsky Normal Form
• Constructive proof (outline):
•
•
•
•
Add a new start symbol S0.
Eliminate all  rules A  .
Eliminate all unit rules A  B.
Convert all remaining rules to the
proper form.
Chomsky Normal Form
• Proof (detailed):
• Add a new start symbol S0.
• Add the rule S0  S.
• Eliminate all  rules A  .
• For each rule A   and each rule
B  uAv, add a rule B  uv.
• Eliminate the rule A  .
Example
• S  SXS | 
• X  ab | 
• Add the rule
• S0  S
Example
• We now have
• S0  S
• S  SXS | 
• X  ab | 
Example
• Apply the rules S   and X  
to the other rules, creating the
rules
•
•
•
•
•
S
S
S
S
S





X
SS
XS
SX
S
• Don’t bother with the last rule.
Example
• Eliminate the rules
•S
•X
Example
• Add the rule
• S0  
because in the original, S could
be replaced by .
Example
• We now have
• S0  S | 
• S  SXS | SS | SX | XS | X
• X  ab
Chomsky Normal Form
• Proof (detailed):
• Eliminate all unit rules A  B.
• If A  B and B  u are rules, then
add the rule A  u.
• Eliminate the rule A  B.
Chomsky Normal Form
• Add the rules
• S  ab
• S0  SXS | SS | SX | XS | X | ab
• Eliminate the rules
• S0  S
•SX
Example
• We now have
• S0  SXS | SS | SX | XS | ab | 
• S  SXS | SS | SX | XS | ab
• X  ab
Chomsky Normal Form
• Eliminate all mixed rules.
•Aa
for all terminals appearing in
strings of length  2.
• Then replace a with A in those
strings.
Example
• Add the rules
•Aa
•Bb
and rewrite the string ab as AB.
Example
• We now have
•
•
•
•
•
S0  SXS | SS | SX | XS | AB | 
S  SXS | SS | SX | XS | AB
X  AB
Aa
Bb
Chomsky Normal Form
• Finally, eliminate all long rules.
• Break all strings of length  2
into a series of strings of length
2.
Chomsky Normal Form
• Replace the rule
• A  B1B2…Bk
with
•
•
•
•
•
A  B1C1
C1  B2C2
…
Ck – 2  Bk – 2Ck – 2
Ck – 1  Bk – 1Bk
Example
• Replace
• S0  SXS
• S  SXS
• with
• S0  SY
• S  SY
• Y  XS
Example
• The final result is
•
•
•
•
•
•
S0  SY | SS | SX | XS | AB | 
S  SY | SS | SX | XS | AB
X  AB
Y  XS
Aa
Bb
A Derivation in CNF
• Use this grammar in CNF to
derive the string ababab.
• S0  SY  SXS  ABXS
 ABABS  ABABAB
 aBABAB  abABAB
 abaBAB  ababAB
ababaB  ababab.
CNF Derivations
• Theorem: If a grammar G is in
CNF and a string w in L(G) has
length n, then w will be derived
from G in exactly 2n – 1 steps.
The Membership
Problem
• This theorem allows us to
determine whether a given
string is derivable from a given
grammar.
• This is called the Membership
Problem.
Example
• Show that the string abba is not
derivable from the grammar of
the previous example.
A Tree of all Possible
Derivations
S0
SY
SY SS
AB XS

SS
AB
SY SS AB ABSS SY
a b
etc.
Example
• Put the grammar
E  E + E | E * E | (E) | a | b | c
into CNF.
• Then show that the string c++ is
not derivable from it.
```