2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Have you tried Myhill-Nerode theorem? $\endgroup$ – Evil Oct 28 '19 at 6:35
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – CS1234 Oct 29 '19 at 4:28
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Try your argument on $L_2 = \{0^i1^j : i \ge j \}$. $\endgroup$ – Yuval Filmus Oct 28 '19 at 7:35
  • $\begingroup$ 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. $\endgroup$ – RandomPerfectHashFunction Oct 28 '19 at 12:24
  • $\begingroup$ The point is that the union of $L_1$ and the new $L_2$ is the language $0^*1^*$, which is regular. $\endgroup$ – Yuval Filmus Oct 28 '19 at 12:30
  • $\begingroup$ 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. $\endgroup$ – RandomPerfectHashFunction Oct 28 '19 at 17:46
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 28 '19 at 18:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.