[Math] Is the example enough for the question below, CFG, Please Help

context-free-grammarexamples-counterexamples

Is my example enough for the question below:

$Question:$

Give a counterexample to show that the following construction fails to prove that
the class of context-free languages is closed under star. Let $A$ be a $CFL$ that is
generated by the $CFG$ $G = (V,\sum,R, S)$. Add the new rule $S \Rightarrow SS$ and call the resulting grammar $G'$. This grammar is supposed to generate $A$*.

$My\ Example:$

Suppose the context-free language A , and the corresponding grammar is
$G = \{\{S\} , \{( , )\} , \{S\Rightarrow (S), S \Rightarrow \epsilon\}, S\}$. Then if we add $S \Rightarrow SS$ and get the new grammar $G'$,
the language generated by G' will have $(()())$ , which is not contained in $A$* . Hence, the new grammar does not generate $A$* in this case.

Best Answer

Your example is OK. However I would add a little explanation why $(()())$ is not in $A^*$, to show you understand, and are not bluffing. But indeed your solution demonstrates that the problem is that $S\to SS$ must only be applied on the top-level and not "deeper" inside derivations. Usually that is enforced by having a new axiom.

Tiny note. I am accustomed to write $\to$ for rules (=productions) and $\Rightarrow$ for derivation steps.

Related Question