Automata

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
		





Quantitative Aptitude
Reasoning
Programming
Interview