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?