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

Question

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?

Answer 1

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. $$

Answer 2

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