Simplifying Grammar

3-Removing ?-productions :
A production A ? ? is called a ?-production.
A variable A is called nullable, if there is a derivation A ?* ?
If G is a CFG and ??L(G), then there exists an equivalent grammar G without ?-productions.
This is an algorithm to eliminate ?-productions from a given grammar.
First: find all nullable variables of G, and put them into the set VN.
1. VN = ?
2. For all ?-production A ? ? , add A to VN.
3. Repeat until closure:
For all productions
B ? A1 A2 ... An and Ai ? VN for i = 1,...,n add B to VN.
4. Determine P based on the productions from P in the following way:
For each production A ? x1 x2 ... xm , m?1, and xi ?(V?T)
add to P this production, as well as all productions, which can construct from this production by substituting nullable variables xi with ?, in all possible combinations, which is equivalent to removing one or the other or all of those variables, i.e. for two nullable variable on the RHS, remove one, remove the other, remove both, remove none. This leads to a bunch of productions, which collect as P . ?-productions A ? ? will not be included in P .
This defines an equivalent grammar G = (V, T, S, P ), i.e. L(G)=L(G ), without ?-productions.
Example 6:
S?ABaC, A?BC, B?b| ?, C?D| ?, D?d
•Nullable set VN={A, B, C}