Problem Detail: 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} Then S —> aSa | B
B —> bB | c The problem I am facing now is how to include ay.
B —> bB | c The problem I am facing now is how to include ay.
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
