0
Explain with an example Chomsky Normal Form

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2014

0
0
• A context-free grammar G = (V, Σ, R, S) is said to be in Chomsky Normal Form (CNF), if and only if every rule in R is of one of the following forms:

1. A → a, for some A ∈ V and some a ∈ Σ
2. A → BC, for some A ∈ V and B, C ∈ V \ {S}
3. S →є

For a Context Free Grammar to be in Chomsky Normal Form(CNF), the grammar should yield productions such as :

A => BC or

A => a

Where a is a terminal and A,B and C are non-terminals

We consider an example

S => bA | aB

A => bAA | aS | a

B => aBB | bS | b

For CNF, A => BC (two nonterminals)

Or

A => a (one terminal)

Consider S => bA

S => BA which is a CNF (substituting B => b)

Consider S => aB

S => AB which is CNF(substituting A => a)

Consider A => aS

Let $C_1$ => a

A => $C_1S$ which is CNF

Consider A =>bAA

A => BAA (substituting B => b)

Let $C_2$ => BA

A => $C_2A$ which is CNF

Consider B => bS

Let $C_3$ => b

B => $C_3S$ which is CNF

Consider B =>aBB

B => ABB (Substituting A =>a)

Let $C_4$ => AB

B => $C_4B$ which is CNF

0