I am trying to teach myself how to write Context-free Grammar for different languages. I have an example language I am trying to work out and this is the answer I came up with, does it make sense?

the language is (i used an image because i don't know how to write out the powers on a mac):

language to be made into cfg

This is my answer:

S --> rSjZr | Z 
Z --> oo

I've been trying to learn it by reading other people's CFG's, however I am still unsure of how it works, my thinking is that, if j and k are 0 then r becomes 0 as well because 2*0 would return 0 and I therefore end up with oo. However, I am unsure about the first part it seems like it could make sense and at the same time it doesn't could somebody please explain to me how they would write a context-free grammar for the language and if my answer makes sense?


  • 1
    $\begingroup$ This question was put on hold, was deleted and is now reposted verbatim. $\endgroup$ – Hendrik Jan Dec 3 '15 at 13:35
  • 1
    $\begingroup$ The question is totally unclear, we cannot help you. In short: what are latters and what are numbers on your description of the language? In particular $j$ seems to be both. Repair that before thinking of writing any grammar at all. $\endgroup$ – Hendrik Jan Dec 3 '15 at 13:39
  • $\begingroup$ Sorry, just fixed it, is it now clear? $\endgroup$ – john3901 Dec 3 '15 at 13:58
  • 1
    $\begingroup$ As @D.W. carefully explained in his comment to the old post: we get questions like this a lot, and we have written hints to solve cf grammars for languages that look just like this: cs.stackexchange.com/q/18524/755 $\endgroup$ – Hendrik Jan Dec 3 '15 at 14:50
  • $\begingroup$ You posted the same thing, and after it was put on hold, you then re-posted it a second time (and then eventually deleted it). Don't do that. Instead, edit the original question. If the edits make the question appropriate here, it can be re-opened after being edited. Deleting the previous copy has the effect of deleting the feedback you got earlier (most of which, incidentally, still applies). $\endgroup$ – D.W. Dec 3 '15 at 20:46

A couple of things:

Sometimes it helps to simplify the description of your grammar. Instead of $\{r^{2j+k}j^ko^2r^j \mid j,k \geq 0 \}$, you can write this: $\{r^{2j}r^kj^koor^j \mid j,k \geq 0\}$. It is still the same grammar, but you can easier see what you're doing. For example, something here stands out: $\{r^{2j}\mathbf{r^k}\mathbf{j^k}oo\mathbf{r^k} \mid j,k \geq 0\}$

Next: Sanity-checking. See if what you're trying to achieve conflicts with any known rules. Can this language be produced by a context-free grammar? Or is this language not context-free? Consider that $\{ a^kb^kc^k \mid k \geq 0\}$ is a classical example for non-context-free grammars (It is context sensitive).

If the language is not context-free, we can stop trying to find a context-free grammar for it. Attempts will be (hopefully) futile.

Unfortunately, I can't provide you with a simple way of constructing grammars for context-free languages. Maybe (probably) some other (far more experienced and knowledgeable) members here might be able to do so. What worked for my (short) stint in TCS, practice helped. I started with simple examples, and increased their complexity. Then you learn to recognize some patterns in languages and solve them for example by splitting the language into multiple, smaller and simpler languages which you already know how to solve.

Lets try to apply that to this case: $\{r^{2j}r^kz^koor^j \mid j,k\geq0\}$ We can see that that is essentially $\{r^{2j}$ [something else] $r^j \mid j\geq0\}$. That is easy to produce:

$S \rightarrow rr X r | X$, where $X$ will produce the [something else]. That something else is of course $r^kz^koo \mid k\geq0$, which is also easy to produce:

$X \rightarrow Y oo | oo$ and

$Y \rightarrow rYz$

Ultimately, the key behind this construction was simplifying the language, and then recognize that the language is a nested variation of $\{a^k\ b\ a^k\}$ and $\{a^k\ b^k\ a\}$, which both are trivial languages to produce.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your reply, could you please edit it, i had made a mistake in my original post and apply your answer to the updated version? $\endgroup$ – john3901 Dec 3 '15 at 14:16
  • $\begingroup$ Small change, big consequence :) I modified the answer accordingly. $\endgroup$ – Mike B. Dec 3 '15 at 14:40

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