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
