Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is my example enough for the question below:


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.

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your example is right.

To ensure you are producing A*, you should add a new start symbol, let s say X and add the rules:

X → XS | epsilon

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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