FOR FREE MATERIALS

Simplification of Context Free Grammar

Type of simplification process:

Sometimes CFG has a different types of useless symbols, unit productions, and null productions. These types of unnecessary symbols and productions increase the number of steps in generating a language from a CFG or any kind of membership test of strings in CFG.   

So, to reduce the complexity of generating language from CFG or membership algorithms, we reduce the unnecessary symbols and productions from CFG.

CFG can be simplified in the following three processes:

1. Elimination or removal of λ – productions.
2. Removal of unit productions like A → B.
3. Removal of useless variables or productions

1.  Elimination or removal of λ – productions

Empty string (λ) which is the part of the language generated from grammar cannot be removed.

If we get this above product then empty string (λ) is part of the language and it cannot be removed.

Variable / Non-Terminal → λ is called null production and λ is not part of the language.

Example:

Consider a grammar, 

Now question is this has null production or not?

Language generated from this grammar is: 

From this language, it is clear that  $\mathbf{\lambda }\mathbf{ }\mathbf{\in }\mathbf{ }\mathbf{L}\mathbf{\left(}{\mathbf{G}}_{\mathbf{1}}\mathbf{\right)}$ so, it is not null production.

Here if we remove λ – production from grammar, then λ is also removed from grammar because $\mathbf{\lambda }\mathbf{ }\mathbf{\in }\mathbf{ }\mathbf{L}\mathbf{\left(}{\mathbf{G}}_{\mathbf{1}}\mathbf{\right)}$.

Another example:

Language generate from this grammar $\mathbf{L}\mathbf{\left(}{\mathbf{G}}_{\mathbf{2}}\mathbf{\right)}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{\left\{}\mathbf{ab}\mathbf{\right\}}$ So, this grammar has a null production. 

This above grammar ${\mathbf{G}}_{\mathbf{2}}$with λ and we remove λ from grammar.

Now,

Example:

Language from this grammar does not contain λ – production because language is L = {ab, a, d}. So, this grammar contains null production.

Now, we remove null or λ production.

S → AB | d | A , A → a, B→b here remove B → λ and put λ wherever B is present. 

Question:

Consider a grammar

Is there null production present?

Solution:

The language generated from this above grammar contains λ. 

Here language L = {ab, d, e, λ}. So,  is part of the language. 

So, this grammar does not contain any null production.