# Simplification Of Cfg

**Simplification of CFG-Introduction**: In a Context Free Grammar (CFG), it may not be necessary to use all the symbols in *V *È*T*, or all the production rules in *P *while deriving sentences. Let us try to eliminate symbols and productions in *G *which are not useful in deriving sentences.

Let *G *= (*V*,*T*, *S*, *P*) be a context-free grammar. Suppose that *P *contains a production of the form

Assume that *A *and *B *are different variables and that

*B* -> *y*1 | *y*2 |. . . | *y**n *|.

is the set of all productions in *P *which have *B *as the left side.

Let be the grammar in which *P *is constructed by deleting

*A*-> *x _{1} B x *2

from *P*, and adding to it

** Substitution Rule**: A production

*A*®

*x Bx*1 2 can be eliminated from a grammar if we put in its place the set of productions in which

*B*is replaced by all strings it derives in one step. In this result, it is necessary that

*A*and

*B*are different variables.

**Abolishing Use less Productions: **In the grammar *G *with *P*,

the production *S ->* *A *does not play any role because *A *cannot be transformed into a terminal string. ‘*A*’ can occur in a string derived from *S*, this can never lead to a sentential form. Hence this production rule can be removed, which does not affect the language.

** Definition**: Let

*G*= (

*V*,

*T*,

*S*,

*P*) be a CFG.

A variable *A*Î*V *is said to be “useful” iff there is at least one *w*Î*L*(*G*) such that

with *x*, *y *in (*V *È*T *)* , i.e., a variable is useful iff it occurs in at least one derivation.

*Illustration: *Consider the grammar *G *with *P*

Here the variable *B *is said to be “useless”, hence the production *B*® *bA *is also “useless”. There is no way to achieve *S *Þ*xBy ** .