Language to CFG ( l + m = 2n )

Question

I'm trying to find the CFG of language

L = {$0^l 1^m 0^n | l+m = 2n$},

I don't know where to start

Answer 1

Whenever you have such an equality in a CFL definition, you probably want to generate equivalent parts of the left-hand side and the right-hand side in one step (or in a fixed sequence of steps). So here, whenever you grow the $l$ you want to grow the "$2n$" by half that amount. The same for $m$ and "2n".

Because the $m$-block is inbetween the one for $l$ and the one for $n$, you need to work on the latter two first. Otherwise you could not coordinate them across an arbitrarily wide block of $1$s.

Look at this derivation: $$S \Rightarrow 00S0 \Rightarrow 0000S00 \Rightarrow 000001A000 \Rightarrow 000001110000. $$

This generates a word from $L$. The rules are linear and can be read from the derivation. They work for the case where $l$ is odd. For even $l$ one need a rule $S \rightarrow 00A0$ or $S \rightarrow 11A0$. And you have to treat very short words and words where $l$ is zero or one. But with this example derivation you hopefully know where and how to start.