3
$\begingroup$

I have this question about closure of a context free grammar, and if someone can check my answer and see if it makes sense, and if not, what is missing, I would be very grateful.

Give an counter-example to show that the following contruction fails in to proof that class of languages free of context is closed under the operation star. By A a language free of context that it is generated by the GLC G = {V,,R,S}. Add the new rule S -> SS e call the resulting grammar G'. That grammar is expected to generate a*"

I have only a superficial comprehension, I believe it is necessary that Rg', the set of production rules of G' must be equal to Rg united with {Sg'->SgSg'|e} or in another words Rg': Rg U {Sg'->SgSg'|e}. Even if that it is correct I don't understand why {Sg'->SgSg'|e} is necessary

$\endgroup$
  • $\begingroup$ Please take more care formatting your question using MathJax; it's hard to read your grammars. $\endgroup$ – Raphael Jan 25 '14 at 16:28
  • $\begingroup$ @Raphael were you able to find another example other than empty string? $\endgroup$ – chibro2 Feb 11 '15 at 3:33
2
$\begingroup$

There is a silly problem that you might need to add a production of the form $S\to\epsilon$, since otherwise you don't necessarily generate $\epsilon$. But the real problem is that $S$ can be used in the right-hand side of productions, and when you add the rule $S\to SS$, things could break. The "correct" way to turn a grammar of $A$ into a grammar of $A^*$ is to add a new start symbol $S'$ and the productions $S' \to S'S|\epsilon$.

In order to find a counterexample, think of the problems mentioned in the previous paragraphs, and try to find an example which manifests them. All it requires is some experimentation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How to be sure that $$ S\to\epsilon$$ wasn't part of the grammar before? And how could $$ S\to SS $$ break things up? I also don't understand why it is $$ S' \to S'S|\epsilon $$ necessary. $\endgroup$ – user2752471 Jan 25 '14 at 23:50
  • $\begingroup$ I suggest you play with some example grammars, trying to modify them in the way of the exercise, and seeing what goes wrong (if anything). This is really the only way to solve this exercise. $\endgroup$ – Yuval Filmus Jan 26 '14 at 1:20
  • $\begingroup$ I hope I save future readers some time: the grammar A -> 0A1, A->Empty, gives an example where the rule A -> AA messes things up. $\endgroup$ – Lorenzo Najt Jun 6 '17 at 0:22

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.