# How to find the Context-free grammars for this language [duplicate]

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

S -> AYCbY|AYbY|YCbY
A->aB|bB
B->aB|bB|_
Y->aY|bY|_


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.

• 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. Apr 6 '15 at 14:56
• 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 7 '15 at 7:31
• Note also that we have extensive reference material collected here.
– 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.