Show that the following construction is not a correct proof for Context Free Grammars

Question

Give a counterexample to show that the following constructions are not correct proofs for the star operation:

Given a CFG $G = (V,Σ,R,S)$, add the new rule i) $ S → SS$ or ii) $S → SS|ε$.

For i), I basically said that this rule is an infinite loop and doesn't contain an epsilon, so can't be the star operation.

For ii) I'm stuck and can't see why it's not equivalent to the star operation

I know the real star operation is $S'→SS'|ε$ but cant seem to see find out why ii) is not the case. I can't find a counterexample.

Any help is hugely appreciated.

Answer 1

$ S\to aSb \mid \varepsilon $.

Hint (due to Klaus Draeger): Consider what happens when you apply transformation (ii) to this grammar. Does the resulting grammar $G'$ satisfy $L(G')=L(G)^*$?

Explanation: The point is that the $S\to SS$ production can be used "inside" the grammar, not just on the "top-level" where it is intended. We can derive $S\to^* aSSb \to^* aababb$ which is of the wrong form. (And the grammar has $S\to\varepsilon$ anyhow.)