0
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\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 '14 at 10:23
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ so $r$ should equals to $p$? $\endgroup$ – Grijesh Chauhan Apr 10 '14 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$ – Grijesh Chauhan Apr 10 '14 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 '14 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$ – Grijesh Chauhan Apr 10 '14 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 '14 at 13:00
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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