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?

  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Apr 10, 2014 at 10:23

2 Answers 2


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$

  • $\begingroup$ so $r$ should equals to $p$? $\endgroup$ Apr 10, 2014 at 12:09
  • $\begingroup$ 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). $\endgroup$ Apr 10, 2014 at 12:17
  • $\begingroup$ @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) $\endgroup$
    – FrankW
    Apr 10, 2014 at 12:54
  • $\begingroup$ @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. $\endgroup$ Apr 10, 2014 at 12:57
  • $\begingroup$ @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. $\endgroup$
    – FrankW
    Apr 10, 2014 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$.

  • $\begingroup$ Do you think the hint is useful?? $\endgroup$ Apr 10, 2014 at 12:19
  • $\begingroup$ @Grijesh Obviously I do. $\endgroup$
    – FrankW
    Apr 10, 2014 at 12:52
  • $\begingroup$ Which hint you think useful one in question, or one in your answer? $\endgroup$ Apr 10, 2014 at 12:54
  • $\begingroup$ your as well as @saadtaame is also correct thanks. $\endgroup$ Apr 10, 2014 at 13:02
  • $\begingroup$ 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. $\endgroup$
    – Sethmo011
    Apr 10, 2014 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.