[Solved]: How to write CFG for languages

Problem Detail: 

How do you write the CFG for the following language:

{a^x b^y c a^x+y}

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

What I tried is:

First I broke a^x+y into a^xa^y which gives:

{a^x b^y c a^xa^y}

Then

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

The problem I am facing now is how to include a^y.

Asked By : Youssef

Answered By : InformedA

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$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33438