Find a CFG for a language

Question

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?

Answer 1

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$

Answer 2

I don't understand what you mean by "chained the productions together" or "imposes order and memory" in your final paragraph.

However, the grammar you give does not work: If you apply the first rule for $A$ multiple times, you will end up with $aa\ldots aaAbBbB\ldots bBbB$ and each $B$ will yield at least one $a$, thus resulting in a word with too many switches from $a$ to $b$ and back.

What you can do is start with $S \rightarrow ABC$ and then have rules that generate the 3 subwords given in the hint from $A$, $B$, and $C$.