Chomsky normal Form and Examples

By: Prof. Dr. Fazal Rehman | Last updated: December 28, 2023

  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₀ H₁ H₀ -> a H₁ -> B

Example 2:

Convert the given CFG into Chomsky normal form

CFG S -> a B c C CFG IN Chomsky normal form S -> H₁ H₀ H₀ -> C H₁ -> H₃ H₂ H₂ -> c H₃ -> H₄ H₅ H₄ -> a H₅ -> 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₀ B | H₁ A A -> a | A H₂ | H₃ B B -> H₅ H₄ H₀ -> H₆ B H₁ -> H₇ A H₂ -> s H₃ -> H₈ B H₄ -> a H₅ -> H₉ H4 H₆ -> H₄ B H₇ -> H₈ A H₈ -> b H₉ -> H₁₁ H₁₀ H₁₀ -> |A H₁₁ -> H₁₂ S H₁₂ -> H₁₃ H₈ H₁₃ -> 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₁ H₀ | H₃ H₂ H₀ -> B H₁ -> H₄ H₀ H₂ -> A H₃ -> H₅ H₂ H₄ -> H₆ H₀ H₅ -> H₇ H₂ H₆ -> a H₇ -> b

Example 5:

CFG conversion into Chomsky normal form

CFG S -> b A A CFG IN Chomsky normal form S -> H₁ H₀ H₀ -> A H₁ -> H₂ H₀ H₂ -> b

Example 6:

CFG conversion into Chomsky normal form

CFG S -> C b A D A CFG IN Chomsky normal form S -> H₁ H₀ H₀ -> A H₁ -> H₃ H₂ H₂ -> D H₃ -> H₄ H₀ H₄ -> H₅ H₆ H₅ -> C H₆ -> b

Example 7:

CFG TO CNF

S -> a B | b d P A CFG IN Chomsky normal form S -> H₀ H₁ | H₃ H₂ H₀ -> a H₁ -> B H₂ -> A H₃ -> H₅ H₄ H₄ -> P H₅ -> H₆ H₇ H₆ -> b H₇ -> 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₀ S H₀ -> H₂ H₁ H₁ -> L H₂ -> H₄ H₃ H₃ -> A H₄ -> H₆ H₅ H₅ -> I H6 -> H₈  H₇ H₇ -> r H₈ -> H₁₀ H₉ H9 -> O H₁₀ -> H₁₂  H₁₁ H₁₁ -> t H₁₂ -> H₁₄  H₁₃ H₁₃ -> U H₁₄ -> H₁₅  H₁₁ H₁₅ -> H₁₆  H₁₇ H₁₆ -> T H₁₇ -> 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₀ S H₀ -> H₂ H₁ H₁ -> L H₂ -> H₄ H₃ H₃ -> A H₄ -> H₆ H₅ H5 -> I H₆ -> H₈ H₇ H₇ -> r H₈ -> H₁₀ H₉ H9 -> O H₁₀ -> H₁₂ H₁₁ H₁₁ -> t H₁₂ -> H₁₄ H₁₃ H13 -> U H₁₄ -> H₁₅ H₁₁ H₁₅ -> H₁₇ H₁₆ H₁₆ -> 4 H₁₇ -> H₁₉ H₁₈ H18 -> T H_{19 –}> H₂₀ H₂₁ H₂₀ -> i H₂₁ -> love