Elimination of null production from context free grammar
If ε belongs to the language then we are supposed to generate it and thus we will not remove it.
Using below example we will understand the whole concept.
Example 1
S -> aSb/aAb/ab/a A -> ε How to know whether ε is generated in the CFG or not ? Find all the Variable which are generating ε So only A is genrating ε Thus ε does not belong to the langauge. Now we will proceed with elimination of NULL production: Replace NULL producing symbol with and without in R.H.S. of remaining states And drop the productions which has ε directly. eg. A -> ε S -> aSb/aAb/ab/ab/a But we no need to write "ab" twice So, S -> aSb/aAb/ab/a
Example 2
S -> AB A -> aAA/ε B -> bBB/ε Nullale Variables are {A, B, S} Because start state also a Nullable symbol so ε belongs to given CFG We will proceed with the method: S -> AB/A/B/ε A -> aAA/aA/a B -> bAA/bA/b