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

B -> H_{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

H_{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