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

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jan 25, 2014 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
    Commented Jan 26, 2014 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$
    – Elle Najt
    Commented Jun 6, 2017 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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