# Binary strings such that the sum of 0's is not equal to twice the sum of 1's

Construct a context-free language for $$L=\{w\in \{0,1\}^* \mid n_0(w)\not= 2n_1(w)\}$$. Here $$n_b(w)$$ is the number of $$b$$'s in $$w$$.

I can construct a CFL in the case $$n_0(w)=2n_1(w)$$, but I have no idea how to construct it when they are not equal, considering that CFL is not closed under complement operation.

Distinguish $$n_0(w) < 2n_1(w)$$ and $$n_0(w) > 2n_1(w)$$. That is, in your grammar for $$n_0(w) = 2n_1(w)$$ either generate extra $$0$$ or (in a separate half of the grammar) extra $$1$$.
• Well, I wonder whether I can do it in the following way. Let $S$ represent strings $n_0(w)=2n_1(w)$, $A$ represent strings $n_0(w)>2n_1(w)$, $B$ represent strings $n_0(w)\ge 2n_1(w)$. Then we can have $A\rightarrow S0B$, $B\rightarrow S|A$. – My_Lulu Apr 15 at 9:36