Normal form for context free grammar AND CNF and GNF

 

Normal form for CFG

Restrict the right hand side of the production rules in different manner this result into different normal form.if CFG and production rule of  grammar satisfy certain restriction then grammar is said to in a normal form.Normal form depending on restrictions applied.

Two normal form for context free grammar

• Chomsky Normal form.(CNF)
• Greibach Normal  form.(GNF)

Chomsky Normal Form

Two types of production rule in Chomsky Normal Form

Case 1:

Right hand side of A-production has single symbol. if A->∝ and ∝ must be terminal .if ∝ is variable then production rule must become a unit production and it is not allowed .

Case 2:

Right hand side of A-production has two or more symbol.

if ∝ is terminal then replace all ∝ by X and  X is a variable.

<variable>-><terminal>

<variable>-><variable><variable>

Example

production 

S->aSa (Not in CNF)

That  production is not in CNF. Convert into CNF.

Solution

Replace the terminal a by new variable A.

get production S->ASA.

Replace SA by a new variable X.

New production rules are

S->AX

X->SA

A->a

That new production rules are in Chomsky Normal Form.

Greibach Normal Form

A CFG in Greibach normal form if all production rules are of type A->a∝ where ∝∈V. GNF is the natural generalization of regular grammar.

• if ∝=ε then |∝|=0 and A production become A->∝ which is type3 production rule.
• if ∝=B where B is a variable in V then |∝|=1 and A->∝B.
• if |∝|>=2 then A->∝B1,∝B2 where B is a variable.

Method to convert CFG into GNF

• Rename all the variables like A1,A2,A3------An.
• Repeat step for i=1,2,3-----n when n is number of variables.
• if A->a∝1,∝2,------- where a∊ ∑  and ∝ is a variable.
• if a is terminal then replace it by a variable.
• if Ai->∝1,∝2,∝3--------∝n where ∝ is variable .if ∝ is same as Ai then remove left recursion.

Example

S->AA|0,A->SS|1

Convert into GNF.

Solution:

Rename S and A by A1 and A2

A1->A2A2|0  and A2->A1A1|1

A1->A2A2 not in GNF

Replace A2 by A1A1 and 1.

A1->A1A1A1|1A2

but production A1->A1A1A1 it is not in GNF has left recursion

A1->1A2A3|0A3

That production in GNF.

Now A2->A1A1 and replacing A1 by 1A2A3 and 0A3

A2->1A2A3A1|0A3A1

A3->1A2A3A2|0A3A2|1A2A3A2A3|0A3A2A3

That production GNF.

Advantage of Normal form

• Avoid left recursion.
• derivation length no longer because remove unit production.
• easily select suitable production in derivation of a string.

Example

Production rule of CFG S->S+S|a|b Find GNF.

Solution

S->S+S not in GNF

that production have left recursion. so remove that left recursion and convert into GNF.

S1->aS2|bS2|a|b

S2->+S1S2|+S1

Now that production rule in GNF.

Normal form are mainly used in grammar to simply the grammar and remove the ambiguity of grammar. because unit production,left recursion,left factor create ambiguity and increase derivation length.So before parsing first grammar is normalized using normal form.