[Solved]: Find a CFG for a language

Problem Detail: 

In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y > x$, $z > w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p b^p)(b^q a^q)(a^r b^r)$.

I've had a go at it, and have come up with

• S -> A
• A -> aAbB | ab
• B -> bBaC | ba
• C -> aCb | ab

This language will give me equal $a$'s and $b$'s. The reason I've chained the productions together is that since $x,y,z,w$ can't be 0, when one production is done, the others must be done as well (that was my thinking). However, I can't help but be worried about order. Even the smallest production won't come out as in the order "abab". Is it possible to construct a CFG that imposes order and memory? Or do I have to go to a PDA then CFG? Or is it irrelevant?

Asked By : Sethmo011

Answered By : saadtaame

The hint is another way of describing the same language. For the two languages to be the same, one must have: $x=p$, $y=p+q$, $z=q+r$, and $w=r$. Notice that these do satisfy the constraints $y\gt x, z\gt w$ and $x+z=y+w$ provided that $q,r\gt 0$. Now the structure of the hint language makes it easy to write a grammar.

$S \to ABA$

$A \to aAb|ab$

$B \to bBa|ba$

Best Answer from StackOverflow

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