Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]

Question

I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, what word should I choose? Or should I use closure-properties and if so what irregularity should I show? I am genuinely so confused. Any help is appreciated.

Answer 1

Let $L = \{0^i1^j : i \neq j\}$. You can prove that $L$ is not regular in many ways. Here are some examples.

Closure properties

If your language were regular then so would $0^*1^* \setminus L$ be, but that language is $\{0^n1^n : n \in \mathbb N\}$, which presumably you already know isn't regular.

Myhill–Nerode

The words $\{0^i : i \in \mathbb N\}$ are pairwise distinguishable modulo $L$: if $i \neq j$, then $0^i1^i \notin L$ but $0^j1^i \in L$. It follows that $L$ isn't regular.

Pumping lemma

If $L$ is regular then it satisfies the pumping lemma, say with constant $n$. Consider the word $w = 0^n 1^{n+n!} \in L$. According to the pumping lemma, there should be a decomposition $w = xyz$ such that $|xy| \leq n$, $|y| \geq 1$, and $xy^iz \in L$ for all $i \in \mathbb N$. Let $|y| = \ell$, so that $y = 0^\ell$. Pick $i = 1 + n!/\ell$. Then $xy^iz = 0^{n+n!} 1^{n+n!} \notin L$, contradicting the pumping lemma.

Answer 2

The language $L=\{0^i 1^j : i \neq j\}$ can be written equivalently as $L=\{0^i 1^j : i \lt j\} \cup \{0^i 1^j : i \gt j\} = L_1 \cup L_2$.

Now if we prove using the Pumping Lemma that either of the languages $L_1$ or $L_2$ are not regular, we are done.

Consider any string
$x = uvw: x \in L_1$.
$u=0^{i-a}$
$ v=0^a1^b$
$w=1^{j-b} : i\lt j, 0 \le a \le i, 0 \le b \le j, a+b\ge 1$.

Now pumping $x$ yields
$ x' = uv^nw = (0^{i-a})(0^a1^b)^n(1^{j-b})$
$ = 0^{i+a(n-1)}1^{j+b(n-1)}: \forall n\ge 0$

For $L_1$ to be regular, $x' \in L_1$,for all arbitrary choices of $i, j, a, b, n$,satisfying the above constraints.

If one chooses $a, b$ such that $a \gt b$, then it is evident that for some $n$, $i+a(n-1) > j + b(n-1)$ (For all $n \gt \frac{j-i}{a-b}-1$ precisely).

Hence, $\exists x' \notin L_1$, and therefore $L_1$ is not regular. This concludes that $L$ is NOT regular.