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

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.

• Have you tried Myhill-Nerode theorem? – Evil Oct 28 '19 at 6:35

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.

• Thank you very much, I understand the basic procedure thanks to you. If I am right, you use closure properties to force your way to an irregular language that we know is irregular. I am still confused about the pumping lemma, but I guess you just get used to it through practice. – CS1234 Oct 29 '19 at 4:28

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.

• Try your argument on $L_2 = \{0^i1^j : i \ge j \}$. – Yuval Filmus Oct 28 '19 at 7:35
• The $L_2$ stated above is with $i \gt j$. Proving non-regularity for the language $\{ 0^i1^j : i \ge j\}$ is trivial since it has the language $\{ 0^i1^j: i = j \}$ as its subset. – RandomPerfectHashFunction Oct 28 '19 at 12:24
• The point is that the union of $L_1$ and the new $L_2$ is the language $0^*1^*$, which is regular. – Yuval Filmus Oct 28 '19 at 12:30
• Yes, that's another alway to think about it. It just works out for $0^*1^*$, since every regular language is also a CFL. But in general the union of two CFLs is another CFL, which need not be a regular language. – RandomPerfectHashFunction Oct 28 '19 at 17:46
• You cannot prove that a language isn’t regular by showing that it has a nonregular subset. It just doesn’t follow. I gave you a counterexample to this technique. – Yuval Filmus Oct 28 '19 at 18:13