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 C1 and C2.
S -> BaABbB
S -> BaC1C2
C1 -> AC2
C2 -> BbB
So, the grammar G2, 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
Ambiguity Grammar
Greibach Normal Form