CREATE OWN LIBRARY

Different forms of CFG

Introduction and Chomsky Normal Form

Context Free Grammar (CFG) has wide usefulness and we can establish many kinds of normal forms of it. Here we consider two of them briefly.

1. Chomsky Normal Form (CNF)
2. Greibach Normal Form (GNF)

1. Chomsky Normal Form (CNF) :

This is one kind of normal form of CFG where the number of symbols on the right of production is strictly limited.

In that case, the string on the right of the production consists of no more than two symbols.

Production of CNF

As we know the general production of CFG: V→ (V ∪ T)*

Now general production of Chomsky Normal Form: V → VV | T

For example:

G1:      S → BC | a

            B → b

            C → c

This above grammar G1 is in CNF.

Another example:

G2:      S → AS | AAS

            A → SA | aa

The above grammar G2 is not in CNF. Because both productions are violating the general production rules of CNF.

Imp: Derivation of string:

To drive any string ω from the production CNF it require (2n – 1) steps, where n = length of ω i.e. n = | ω|

Example:

i.e. (2n – 1 ) = 3

i.e. (2n – 1 ) = 2 * 3 – 1 = 5

So, the number of steps required to derive a string by CNF is (2n – 1) where n = |ω|. 

Application of CNF:

We used Chomsky Normal Form whether a string is in the grammar or not. Basically, we used the membership algorithm CYK to check whether a string in the grammar or not and it takes $\mathbf{O}\mathbf{\left(}{\mathbf{\omega }}^{\mathbf{3}}\mathbf{\right)}$ time to check the membership. 

This algorithm works only if the grammar is in Chomsky Normal Form.

So, initially, we convert CFG to CNF after that apply the membership algorithm CYK.