Is the language $L = \{0^m1^n: m \neq n - 1 \}$ context free?

Question

Consider the language: $L = \{0^m1^n : m \neq n - 1 \}$ where $m, n \geq 0$
I tried for hours and hours but couldn't find its context free grammar. I was stuck with a rule which can check on the condition $m \neq n - 1$. Would anyone can help me out? Thanks in advance.

Answer 1

The trick is that you need extra "clock" letters $a,b, \dots$ in the language with non-reversible transformations between them, to define the different phases of the algorithm that builds the string. When the first phase is done, transform $a \to b$, then $b \to c$ after phase 2, etc, then finally remove the extra letters to leave a 0-1 string. The natural place for these extra markers is between the 0's and the 1's, or before the 0's, or after the 1's.

The string can be built by first deciding whether $m - (n-1)$ will be positive or negative, then building a chain of 0's (resp. 1's) of some length, then inserting 01's in the "middle" of the string several times. Each of these steps can be encoded by production rules using extra letters in addition to 0 and 1.

Answer 2

Write grammars for languages $\{0^m 1^n \colon m < n-1\}$ and $\{0^m 1^n \colon m > n-1\}$ and create their sum. As a simplification, you can try to write grammar for $\{0^m 1^n \colon m \leq n\}$ first.