How do you write the CFG for the following language:

{ax by c ax+y}

Is there some formula or rules I need to follow? An explanation will be so appreciated.

What I tried is:

First I broke ax+y into axay which gives:

{ax by c axay}


S ---> aSa | B
B ---> bB | c

The problem I am facing now is how to include ay.

  • 1
    $\begingroup$ Unfortunately, there is no recipe. It is like dancing or riding a bicycle, you learn by practicing. You have to get an intuition for how the CFG can be used. Try to do first the following language: $\{a^xca^x\mid x\geq 1\}$, then $\{a^xcb^x\mid\ldots\}$, then $\{a^xa^yca^xa^y\mid\ldots\}$, then $\{a^xa^yca^{x+y}\mid\ldots\}$. That should put you on track. Also try it with $x\geq 0$ and with $x\geq 1$, and same for $y$. $\endgroup$ – babou Nov 23 '14 at 16:38

As per advice from others:

Rewrite into $a^xb^yca^ya^x$.

Now it is easy to see the nested structure (or symmetry in the exponent)

So we will have

  • $S_1 \rightarrow a S_1 a$ $|$ $S_2$
  • $S_2 \rightarrow b S_2 a$ $|$ $c$

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