Chomsky Normal Form

In Automata, every grammar in Chomsky Normal Form is context-free. So, every context free grammar can be converted into Chomsky Normal Form. The name Chomsky Normal Form came from Noam Chomsky, who is an American linguist, philosopher and scientist. He had modelled knowledge of the language using formal grammars. He claimed that with the help of formal grammar, we can produce an infinite number of sentences with a limited set of grammatical rules. There are some conditions of grammar to belong in Chomsky Normal Form.

A context free grammar G = (V,Σ,P,S) is said to be in Chomsky Normal Form if all of its production rules are in the form.

A → BC, 
A → a, 
S → ε

Here, A, B and C are non-terminal symbols, where A,B,C ∈ N,
a is the terminal symbol, where a ∈ Σ,
S is the start symbol, where S → ε and
ε is the empty string.

We can also say that any language (L) without any production is generated by the grammar G in which the productions are in the above form.

Process to find Context Free Grammar in Chomsky Normal Form

The context free grammar, under Chomsky Normal Form is formed with no unit productions, if any and the right hand side of any production has a single terminal or two or more symbols.

Example to find a Grammar in Chomsky Normal Form

Suppose there is a grammar G with the productions P given by,

S -> aAbB 

A -> aA|a 

B -> bB|b

There, we have given productions in proper form -

A -> a 

B -> b

There is no productions in the set P.

Ba -> a 

Bb -> b 

// For S -> aAbB, we have
S -> BaABbB, 

// For A -> aA 
A -> BaA, 

// For B -> bB 
B -> BbB

In the above, we have only the following in non proper form-

S -> BaABbB

Let's taken two variables C₁ and C₂.

S -> BaABbB

S -> BaC1C2

C1 -> AC2

C2 -> BbB

So, the grammar G₂, in Chomsky Normal Form with the productions written as -

S -> BaC1C2

C1 -> AC2

C2 -> BbB

A -> BaA

B -> BbB

Ba -> a,

Bb -> b,

A -> a,

B -> b