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

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.

-
Try making a PDA for it. – Unreasonable Sin Aug 11 '11 at 3:15
It's a bit late now, but in your title, a language is a set of strings. That's not the same thing as a grammar. A better choice would be "Is the language (...) context-free?" – Rick Decker Jun 8 '12 at 18:04
@vonbrand: It's one thing to fix small errors in new posts (i.e. posts from the past day or two), but it's another to bump something from two and a half years ago just to remove one word from the title. – Asaf Karagila Feb 9 '13 at 2:36
@AsafKaragila, sorry about that. Really didn't look at the dates. – vonbrand Feb 9 '13 at 2:39

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