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 -> H8 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