Chomsky Normal Form

for
Context Free Grammars
Chomsky Normal Form

• A particular form of a CFG which is

useful for understanding CFGs and
proving things about them.
 Chomsky Normal Form

Each production has form:

A → BC or A→a

variable variable terminal

B and C are not the start variable.

We permit S → 𝜀 where S is the start variable.
Conversion to Chomsky Normal Form

Is it possible to convert an arbitrary

CFG into an equivalent grammar which is
of the Chomsky normal form?

✓ Yes
 Conversion to Chomsky Normal Form

Example: S → ASB
A → aAS | a | 𝜀 Not Chomsky
B → SbS | A | bb Normal Form

We will convert it to Chomsky Normal Form

 Add a new start variable

S0 → S
S → ASB
A → aAS | a | 𝜀
B → SbS | A | bb

This way, the start variable does not occur on the right
hand side of a rule.
 Eliminate the 𝜀 rules

S0 → S S0 → S
S → ASB S → ASB | SB
A → aAS | a | 𝜀 A → aAS | a | aS
B → SbS | A | bb B → SbS | A | bb | 𝜀

Remove the rule

A→𝜀
 Eliminate the 𝜀 rules

S0 → S S0 → S
S → ASB | SB S → ASB | SB | AS | S
A → aAS | a | aS A → aAS | a | aS
B → SbS | A | bb | 𝜀 B → SbS | A | bb

Remove the rule

B→𝜀
 Remove unit rules

S0 → S S0 → S
S → ASB | SB | AS | S S → ASB | SB | AS | S
A → aAS | a | aS A → aAS | a | aS
B → SbS | A | bb B → SbS | bb | aAS | a | aS

Remove the rule

B→A
 Remove unit rules

S0 → S S0 → S
S → ASB | SB | AS | S S → ASB | SB | AS
A → aAS | a | aS A → aAS | a | aS
B → SbS | bb | aAS | a | aS B → SbS | bb | aAS | a | aS

Remove the rule

S→S
 Remove unit rules

S0 → S S0 → ASB | SB | AS
S → ASB | SB | AS S → ASB | SB | AS
A → aAS | a | aS A → aAS | a | aS
B → SbS | bb | aAS | a | aS B → SbS | bb | aAS | a | aS

Remove the rule

S0 → S
Introduce new variables for the terminals:

S0 → ASB | SB | AS S0 → ASB | SB | AS
S → ASB | SB | AS S → ASB | SB | AS
A → aAS | a | aS A → V1AS | a | V1S
B → SbS | bb | aAS | a | aS B → SV2S | V2V2 | V1AS | a | V1S
V1 → a
V2 → b
For every symbol: a
New variable: 𝑉𝑖
Add production 𝑉𝑖 → 𝑎

In productions with length at least 2

replace a with 𝑉𝑖

Productions of form A → a
do not need to change!
Introduce new intermediate variable U1
to break the production: S0 → ASB

S0 → ASB | SB | AS S0 → AU1 | SB | AS
S → ASB | SB | AS S → ASB | SB | AS
A → V1AS | a | V1S A → V1AS | a | V1S
B → SV2S | V2V2 | V1AS | a | V1S B → SV2S | V2V2 | V1AS | a | V1S
V1 → a V1 → a
V2 → b V2 → b
U1 → SB
Introduce new intermediate variable U2
to break the production: S → ASB

S0 → AU1 | SB | AS S0 → AU1 | SB | AS
S → ASB | SB | AS S → AU2 | SB | AS
A → V1AS | a | V1S A → V1AS | a | V1S
B → SV2S | V2V2 | V1AS | a | V1S B → SV2S | V2V2 | V1AS | a | V1S
V1 → a V1 → a
V2 → b V2 → b
U1 → SB U1 → SB
U2 → SB
Introduce new intermediate variable U3
to break the production: A → V1AS

S0 → AU1 | SB | AS S0 → AU1 | SB | AS
S → AU2 | SB | AS S → AU2 | SB | AS
A → V1AS | a | V1S A → V1U3 | a | V1S
B → SV2S | V2V2 | V1AS | a | V1S B → SV2S | V2V2 | V1AS | a | V1S
V1 → a V1 → a
V2 → b V2 → b
U1 → SB U1 → SB
U2 → SB U2 → SB
U3 → AS
Introduce new intermediate variable U4
to break the production: B → SV2S

S0 → AU1 | SB | AS S0 → AU1 | SB | AS
S → AU2 | SB | AS S → AU2 | SB | AS
A → V1U3 | a | V1S A → V1U3 | a | V1S
B → SV2S | V2V2 | V1AS | a | V1S B → SU4 | V2V2 | V1AS | a | V1S
V1 → a V1 → a
V2 → b V2 → b
U1 → SB U1 → SB
U2 → SB U2 → SB
U3 → AS U3 → AS
U4 → V2S
Introduce new intermediate variable U5
to break the production: B → V1AS

S0 → AU1 | SB | AS S0 → AU1 | SB | AS
S → AU2 | SB | AS S → AU2 | SB | AS
A → V1U3 | a | V1S A → V1U3 | a | V1S
B → SU4 | V2V2 | V1AS | a | V1S B → SU4 | V2V2 | V1U5 | a | V1S
V1 → a V1 → a
V2 → b V2 → b
U1 → SB U1 → SB
U2 → SB U2 → SB
U3 → AS U3 → AS
U4 → V2S U4 → V2S
U5 → AS
Replace any production 𝐴 → 𝐶1 𝐶2 … 𝐶𝑛

with 𝐴 → 𝐶1 𝑈1
𝑈1 → 𝐶2 𝑈2
…
𝑈𝑛−2 → 𝐶𝑛−1 𝐶𝑛

New intermediate variables: 𝑈1 , 𝑈2 , … , 𝑈𝑛−2

 Final grammar in Chomsky Normal Form:

S0 → AU1 | SB | AS
S → AU2 | SB | AS
A → V1U3 | a | V1S
B → SU4 | V2V2 | V1U5 | a | V1S
Initial grammar V1 → a
V2 → b
S → ASB U1 → SB
A → aAS | a | 𝜀 U2 → SB
B → SbS | A | bb U3 → AS
U4 → V2S
U5 → AS