CNF stands for Chomsky normal form. A CFG(context-free grammar) is in Chomsky normal form if all production rules of the CFG must fulfill one of the following conditions;

- Start symbol generating ε. For example, A → ε.
- A non-terminal generating two non-terminals. For example, S → AB.
- A non-terminal generating a terminal. For example, S → a.

## Example 1:

## What is the Chomsky normal form for the following CFG?

**CFG**

S -> a B

**CFG IN Chomsky normal form**

S -> H_{0} H_{1}

H_{0} -> a

H_{1} -> B

## Example 2:

## Convert the given CFG into Chomsky normal form

**CFG**

S -> a B c C

**CFG IN Chomsky normal form**

S -> H_{1} H_{0}

H_{0} -> C

H_{1} -> H_{3} H_{2}

H_{2} -> c

H_{3} -> H_{4} H_{5}

H_{4} -> a

H_{5} -> B

## Example 3:

## Convert the following CFG into Chomsky normal form

**CFG**

S -> a B B B | b A A A

A -> a | A s | b B B

B -> b| b S |A a a

**CFG IN Chomsky normal form**

S -> H_{0} B | H_{1} A

A -> a | A H_{2 }| H_{3} B

_{5}H

_{4}

H

_{0}-> H

_{6}B

H

_{1}-> H

_{7}A

H

_{2}-> s

H

_{3}-> H

_{8}B

H

_{4}-> a

H

_{5}-> H

_{9}H4

H

_{6 }-> H

_{4}B

H

_{7}-> H

_{8}A

H

_{8}-> b

H

_{9}-> H

_{11}H

_{10}

H

_{10}-> |A

H

_{11}-> H

_{12}S

H

_{12}-> H

_{13}H

_{8}

H

_{13}-> b|

## Example 4:

## Convert the following CFG into Chomsky normal form

**CFG**

S -> a B B B | b A A A

**CFG IN Chomsky normal form**

S -> H_{1} H_{0 }| H_{3} H_{2}

H_{0} -> B

H_{1} -> H_{4} H_{0}

H_{2} -> A

H_{3} -> H_{5} H_{2}

H_{4} -> H_{6} H_{0}

H_{5} -> H_{7} H_{2}

H_{6} -> a

H_{7} -> b

## Example 5:

## CFG conversion into Chomsky normal form

**CFG**

S -> b A A

**CFG IN Chomsky normal form**

S -> H_{1} H_{0}

H_{0} -> A

H_{1} -> H_{2} H_{0}

H_{2} -> b

## Example 6:

## CFG conversion into Chomsky normal form

**CFG**

S -> C b A D A

**CFG IN Chomsky normal form**

S -> H_{1} H_{0}

H_{0} -> A

H_{1} -> H_{3} H_{2}

H_{2} -> D

H_{3} -> H_{4} H_{0}

H_{4} -> H_{5} H_{6}

H_{5} -> C

H_{6} -> b

## Example 7:

## CFG TO CNF

S -> a B | b d P A

**CFG IN Chomsky normal form**

S -> H_{0} H_{1 }| H_{3} H_{2}

H_{0} -> a

H_{1} -> B

H_{2} -> A

H_{3} -> H_{5} H_{4}

H_{4} -> P

H_{5} -> H_{6} H_{7}

H_{6} -> b

H_{7} -> d

## Example 8:

## CFG TO CNF

S -> T 4 t U t O r I A L S

**CFG IN Chomsky normal form**

S -> H_{0} S

H_{0} -> H_{2} H_{1}

H_{1} -> L

H_{2} -> H_{4} H_{3}

H_{3} -> A

H_{4} -> H_{6} H_{5}

H_{5} -> I

H6 -> H_{8 } H_{7}

H_{7} -> r

H_{8} -> H_{10 }H_{9}

H9 -> O

H_{10} -> H_{12 } H_{11}

H_{11} -> t

H_{12} -> H_{14} H_{13}

H_{13} -> U

H_{14} -> H_{15 } H_{11}

H_{15} -> H_{16 } H_{17}

H_{16} -> T

H_{17} -> 4

## Example 9:

## CFG TO CNF

S -> i love T 4 t U t O r I A L S

**CFG IN Chomsky normal form**

S -> H_{0} S

H_{0} -> H_{2} H_{1}

H_{1} -> L

H_{2} -> H_{4} H_{3}

H_{3} -> A

H_{4} -> H_{6} H_{5}

H5 -> I

_{6}-> H

_{8}H

_{7}

H

_{7}-> r

H

_{8}-> H

_{10}H

_{9}

H9 -> O

H

_{10}-> H

_{12}H

_{11}

H

_{11}-> t

H

_{12}-> H

_{14}H

_{13}

H13 -> U

H

_{14}-> H

_{15}H

_{11}

H

_{15}-> H

_{17}H

_{16}

H

_{16}-> 4

H

_{17}-> H

_{19}H

_{18}

H18 -> T

H

_{19 –}> H

_{20}H

_{21}

H

_{20}-> i

H

_{21}-> love