give a context-free grammar describing the language L={w∈{a,b}∗∣w is of the form xby, where |x|>|y|}.

I had one solution like this


but it was complaining that it accepts the language babbabaaaaa which is not belonging to the language. Anyone knows how to solve this? and I have no idea how it produces babbabaaaaa, if each time both Ys follows the same rule.

  • $\begingroup$ Quote:"if each time both $Y$s follows the same rule" The point with CF grammars is that we cannot force the $Y$'s to follow the same rule each time. That would require a much stronger grammar type. So you have to fine another mechanism to keep track of the $|x|>|y|$ requirement in your language. In fact your grammar will generate a regular language as you do not use "real" recursion. $\endgroup$ Apr 6 '15 at 14:56
  • $\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 7 '15 at 7:31
  • 1
    $\begingroup$ Note also that we have extensive reference material collected here. $\endgroup$
    – Raphael
    Apr 7 '15 at 7:33

One helpful technique is to decompose a problem like this into the concatenation of two subproblems, each of which can be generated by a simpler grammar. In this case, a string $xby$ with $|x|\ge|y|$ can be written as $uvby$ with $|u|\ge 1$ and $|v|=|y|$. The reason for doing this is that the $u$ part (all strings over $a,b$ of length at least 1) can be generated by $$ A\rightarrow aA\mid bA\mid a\mid b $$ and the $vby$ part (where $v$ and $y$ have the same length) can be generated (from inside out, starting with the central $b$) by $$ B\rightarrow aBa\mid aBb\mid bBa\mid bBb\mid b $$ Now just make a grammar from the concatenation of the $A$ part followed by the $B$ part.

You might want to look at this answer.


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