# Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?

I have been trying to find a a CFG for this language generated.

I came to the conclusion that I need three parts

1. When $$i \le j$$
2. When $$j < 2j < i$$
3. When $$j < i < 2j$$

I was able to come up the production rules for 1 and 2 but I'm getting stuck at 3.

I thought I found a solution in Context Free Grammar for $$\{a^ib^j | i,j ≥ 0; i ≠ 2j\}$$, but when I tried for $$0^81^5$$ it didn't work.

I was however able to come up with a CSG.

Do you know how to solve this?

• Does this answer your question? Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j} Feb 10 at 10:11
• What evidence do you have that the linked answer doesn't generate $0^81^5$?
– rici
Feb 10 at 13:53
• Specifically, in the grammar in the accepted answer, the derivation is $S\to S_2, S_2\to Bb$ and then $B\to aaBb$ four times, and finally $B\to\varepsilon$.
– rici
Feb 10 at 14:51

I will only argue about 3), since this is the case you're having troubles with.

Consider $$\{ 0^i 1^j \mid j \le i \le 2j \}$$ for a moment. You can get a CFG for this language by noticing that you can "match" each occurrence of a $$1$$ to either $$1$$ or $$2$$ occurrences of $$0$$s (in such a way that every occurrence of $$0$$ is matched exactly to a single occurrence of $$1$$).

$$S \to 0S1 \mid 00S1 \mid \varepsilon$$

To get a CFG for $$\{ 0^i 1^j \mid j < i < 2j \}$$ you just need to ensure that a) there is at least one $$1$$ matched to a single $$0$$, and b) there is at least one $$1$$ matched to two $$0$$s.

Since using the order of the rules is irrelevant and using $$S \to 0S1$$ followed $$S \to S \to 00S1$$ generates $$3$$ zeros and $$2$$ ones, we can simulate the execution of these rules as the last step each possible derivation by replacing $$S \to \varepsilon$$ with $$S \to 00011$$. To summarize, the final grammar is: $$S \to 0S1 \mid 00S1 \mid 00011.$$

You only need a grammar for i < 2j and i > 2j. Have a symbol X that gets converted to 0, 01, 0X, 0X1 or 0X11, so j < 2i. And a symbol Y that gets converted to 1 or 0Y11Z, with Z converted to eps or Z1, so j > 2i.

S -> X | Y
X -> 0 | 01 | 0X | 0X1 | 0x11
Y -> 1 | 0Y11Z
Z -> eps | Z1