Theory of Automata

Remove Null Production from CFG



Sometimes some production rules of CFGs containing redundant null (epsilon) moves. In some cases (but not always), We can  remove  all these redundant Null productions from a CFG .  

IF G1 and is the CFG which is containing the redundant null moves and G2 is the CFG which is derived from G1 after removal redundant null Production, Then 

G1 must be equal to G2 (i.e. G1=G2).

Because any of two grammars are considered equivalent if they are produce the same language.

 Cases to Remove Null Productions

It is not possible in every case that a null production is eliminated from CFG. Let explain all



Case 01: If the Null (epsilon) move is the part of each string which derived from given CFG, then Null move cannot remove from that CFG.

Example

Consider a Context free grammar (G1) with the following production rules

  • S → aS | A
  • A → ε

After Simplification Context free Grammar (G2) is given below

  • S → aS | a | ε

So, We cannot remove null production from given grammar (G1) because Null (epsilon) move is the part of each string which derived from given CFG.

Case 02: And If the Null (epsilon) move is not the part of each string which derived from given CFG, then Null move can be removed from that CFG.



Consider a CFG with the following production rules

  • S → ABC
  • A → aA | ε
  • B→ bB | ε
  • C → c

After Simplification Context free Grammar (G2) is given below

  • S → ABC | BC | AC | C
  • A → aA | a
  • B→ bB | b
  • C → c

As We can remove all null production from given grammar (G1) because Null (epsilon) move is not the part of any string which derived from given CFG. G1 and G2 also generating the same results as well.

Method to Remove Null Production is explained in very next lecture.

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest