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.


$ 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.