The equivalent grammar, free of ε-productions, corresponding to the grammar G:…

Concept — eliminating ε-productions

A nonterminal is called nullable if it can derive the empty string, either directly through a production X → ε or through a chain of productions whose right-hand sides consist only of nullable symbols. To obtain an equivalent grammar with no ε-productions, delete every production of the form X → ε and, for each surviving production, add every variant formed by omitting one or more nullable occurrences from its right-hand side; a non-start nonterminal is never left with an empty right-hand side. The resulting grammar generates exactly the same language, apart from the empty string itself.

Application to G

1. Nullable symbols: B → ε makes B nullable. In A → BB both occurrences are nullable, so A is nullable as well. The only S-production is S → aA, which always keeps the terminal a, so S is not nullable. Hence the nullable set is {A, B}.

2. Rewrite S → aA: the single nullable occurrence A may be omitted, which adds S → a. This yields S → a | aA.

3. Rewrite A → BB: omitting either one of the two nullable B symbols adds A → B; omitting both would leave an empty right-hand side, which is not permitted for this nonterminal. This yields A → BB | B.

4. Rewrite B → aBb: omitting the nullable B adds B → ab. The production B → ε is now deleted. This yields B → aBb | ab.

5. Collecting the surviving productions gives S → a | aA, A → BB | B, B → aBb | ab.

Cross-check by language

In G, B derives anbn for n ≥ 0, so A → BB derives aibiajbj with i, j ≥ 0, and S → aA derives a followed by that string. In the rewritten grammar B derives anbn for n ≥ 1, A → BB | B supplies one or two such blocks, and S → a | aA supplies the case in which both blocks vanish. Both grammars therefore generate the same set of strings. For example, aab is obtained in G as S ⇒ aA ⇒ aBB ⇒ a·ab·ε = aab, and in the rewritten grammar as S ⇒ aA ⇒ aB ⇒ a·ab = aab.

Contrast with the other production sets

• In S → aA, A → BB, B → aBb the symbol B has aBb as its only production, so every expansion of B reintroduces B and no terminal string can be completed.

• In S → a | aA, A → BB, B → aBb | ab the only A-production is A → BB, so every derivation that passes through A must contain two anbn blocks, and a string such as aab, which needs a single block, cannot be produced.

• In S → a | aA, A → BB | B, B → aBb the symbol B again has no terminating alternative, so a is the only string the set can derive.