# 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**.

##### B_{a} -> a
B_{b} -> b
// For S -> aAbB, we have
S -> B_{a}AB_{b}B,
// For A -> aA
A -> B_{a}A,
// For B -> bB
B -> B_{b}B

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

##### S -> B_{a}AB_{b}B

Let's taken two variables C_{1} and C_{2}.

##### S -> B_{a}AB_{b}B
S -> B_{a}C_{1}C_{2}
C_{1} -> AC_{2}
C_{2} -> B_{b}B

So, the grammar G_{2}, in Chomsky Normal Form with the productions written as -

##### S -> B_{a}C_{1}C_{2}
C_{1} -> AC_{2}
C_{2} -> B_{b}B
A -> B_{a}A
B -> B_{b}B
B_{a} -> a,
B_{b} -> b,
A -> a,
B -> b

Ambiguity Grammar

Greibach Normal Form