# Find a CFG for a language

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?

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Apr 10 '14 at 10:23

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$

• so $r$ should equals to $p$? – Grijesh Chauhan Apr 10 '14 at 12:09
• think of PDA, you push all '$a$'s to compare with number of '$b$'s you pop '$a$', Now have lost prefix sub-string $a^xb^y$ in PDS (I don't think hint is correct). – Grijesh Chauhan Apr 10 '14 at 12:17
• @Grijesh $r$ and $p$ are independent of each other. The only requirement is that both are greater than 0. (Otherwise $x$ resp. $w$ wouldn't be) – FrankW Apr 10 '14 at 12:54
• @FrankW May be I am wrong, I request you please read first statement in question. I don't think language is CFL (also i think hint given in question is wrong, that the reason I commented you). Correct me if I am wrong. – Grijesh Chauhan Apr 10 '14 at 12:57
• @Grijesh I reread it after seeing your comments. I am absolutely sure that the hint from the question is correct and the language is CFL. – FrankW Apr 10 '14 at 13:00

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$.

• Do you think the hint is useful?? – Grijesh Chauhan Apr 10 '14 at 12:19
• @Grijesh Obviously I do. – FrankW Apr 10 '14 at 12:52
• Which hint you think useful one in question, or one in your answer? – Grijesh Chauhan Apr 10 '14 at 12:54
• your as well as @saadtaame is also correct thanks. – Grijesh Chauhan Apr 10 '14 at 13:02
• What I meant by chaining was forcing A to generate a B and forcing B to generate a C, my vocab is pretty poor in that department. With regards to order and memory, if I converted this to a PDA, I'd be able to use the stack to remember x,y,z,w so I could accept words in the order abab. But with a CFG, I can't figure out how I'd force the productions to come out a^x b^y a^z b^w (abab). I don't know if that's clearer. – Sethmo011 Apr 10 '14 at 13:38