Chomsky normal Form and Examples

By Prof. Fazal Rehman Shamil
Last modified on January 25th, 2021

 

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 -> H0 H1
H0 -> a
H1 -> B

Example 2:

Convert the given CFG into Chomsky normal form

CFG

S -> a B c C

CFG IN Chomsky normal form

S -> H1 H0
H0 -> C
H1 -> H3 H2
H2 -> c
H3 -> H4 H5
H4 -> a
H5 -> 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 -> H0 B | H1 A
A -> a | A H2 | H3 B
B -> H5 H4
H0 -> H6 B
H1 -> H7 A
H2 -> s
H3 -> H8 B
H4 -> a
H5 -> H9 H4
H6 -> H4 B
H7 -> H8 A
H8 -> b
H9 -> H11 H10
H10 -> |A
H11 -> H12 S
H12 -> H13 H8
H13 -> 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 -> H1 H0 | H3 H2
H0 -> B
H1 -> H4 H0
H2 -> A
H3 -> H5 H2
H4 -> H6 H0
H5 -> H7 H2
H6 -> a
H7 -> b

Example 5:

CFG conversion into Chomsky normal form

CFG

S -> b A A

CFG IN Chomsky normal form

S -> H1 H0
H0 -> A
H1 -> H2 H0
H2 -> b

Example 6:

CFG conversion into Chomsky normal form

CFG

S -> C b A D A

CFG IN Chomsky normal form

S -> H1 H0
H0 -> A
H1 -> H3 H2
H2 -> D
H3 -> H4 H0
H4 -> H5 H6
H5 -> C
H6 -> b

Example 7:

CFG TO CNF

S -> a B | b d P A

CFG IN Chomsky normal form

S -> H0 H1 | H3 H2
H0 -> a
H1 -> B
H2 -> A
H3 -> H5 H4
H4 -> P
H5 -> H6 H7
H6 -> b
H7 -> d

Example 8:

CFG TO CNF

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

CFG IN Chomsky normal form

S -> H0 S
H0 -> H2 H1
H1 -> L
H2 -> H4 H3
H3 -> A
H4 -> H6 H5
H5 -> I
H6 -> H H7
H7 -> r
H8 -> H10 H9
H9 -> O
H10 -> H12  H11
H11 -> t
H12 -> H14  H13
H13 -> U
H14 -> H15  H11
H15 -> H16  H17
H16 -> T
H17 -> 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 -> H0 S
H0 -> H2 H1
H1 -> L
H2 -> H4 H3
H3 -> A
H4 -> H6 H5
H5 -> I
H6 -> H8 H7
H7 -> r
H8 -> H10 H9
H9 -> O
H10 -> H12 H11
H11 -> t
H12 -> H14 H13
H13 -> U
H14 -> H15 H11
H15 -> H17 H16
H16 -> 4
H17 -> H19 H18
H18 -> T
H19 –> H20 H21
H20 -> i
H21 -> love

Prof.Fazal Rehman Shamil (Available for Professional Discussions)
1. Message on Facebook page for discussions,
2. Video lectures on Youtube
3. Email is only for Advertisement/business enquiries.