I will explain with examples
1. LET G be any context-free grammar with (lambda) not in L(G).Then there exist an equivalent grammar G' having no (lambda) production.
G:
S → ASA | BaB | b,
A → B,
B → b
B → ∈
Clearly S does not derive ∈. So ∈ is not in L(G). Now we need to eliminate B → ∈. So we substitute B = ∈ in RHS of each production (where B occurs).
Putting B = ∈ in the following productions we can get new additional productions.
A → B ===> A → ∈
S → BaB ===> S → aB (Putting ∈ in first B)
S → BaB ===> S → Ba (Putting ∈ in second B)
S → BaB ===> S → a (Putting ∈ in both B's).
So if we remove the production B → ∈ from G we will have add these new productions to G. So new Grammar G' is:
S → ASA | BaB | aB | Ba | a | b,
A → ∈ ,
A → b
B → b
But our new Grammar G' contains another null production A → ∈ . If we eliminate this null production we will add the following new productions.
S → ASA ===> S → SA
S → ASA ===> S → AS
S → ASA ===> S → S (This is redundant)
So our new Grammar G'' is
S → ASA | AS | SA | BaB | aB | Ba | a | b,
A → ,b
B → b
But If ∈ is in L(G) then we could not completely eliminate null productions because we will not be able to derive ∈ itself.
2. let G be any CFG without (lambda production). Then there exist a CFG G' that does not have any unit production equivalent to G
A unit production is of the form A → B where both A and B are non terminals. To eliminate this unit production, for each B → alpha add a new production A → alpha.
For example:
A → a
A → B
B → c
B → dC
C → aB
To eliminate A → B we need to add the following new productions to G.
A → c
A → dC
So equivalent grammar G' without unit productions is:
A → a
A → c
A → dC
B → c
B → dC
C → aB
The logic is same as the proof in Peter Linz but less formal
