Verification wanted: Show the language $L=\{0^m1^n \enspace | \enspace m \neq n\}$ is not regular [closed]

Question

$$L=\{0^m1^n \enspace | \enspace m \neq n\}$$

I saw that this exact question exists elsewhere, but I couldn't understand what was being said there. My question does not mandate the use of the Pumping Lemma as stated "elsewhere", but I am using the Pumping Lemma anyway. I want to present what I have so far, and for someone to tell me if I'm on the right track:

1. Assume $L$ is not regular.
2. Let $p$ be the pumping length given by the Pumping Lemma for regular languages.
3. Let the string $w = 0^p1^{p+1} \in L$
4. By the Pumping Lemma, $w = xy^iz$, where $i \geq 0$, $\color{green}{\lvert y \rvert \geq 1}$, and $\color{red}{\lvert xy \rvert \lt p}$.
5. Let:

\begin{equation} \begin{aligned} \mathcal{x} &= \mathcal{0}^{p} \\ {y} & = {1}^{p+1} \\ {z} & = \varepsilon \end{aligned} \end{equation}

It is at this point in the proof that I get confused. I feel as if I've set it up well, but just can't finish. Here's what I've got, though:

6. We see that $\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$
7. However, $\lvert xy \rvert= p+p+1 \gt p \enspace \color{red}{\textbf{X}}$

As we can see by $\textit{(7)}$, our test string $w$ violates a $\color{red}{condition}$ of the Pumping Lemma, thus is not regular.

Thumbs up, thumbs down, anyone? Did I make the appropriate inferences about my split string $w$ in order to achieve a contradiction, and did I even split the string correctly? And to boot, did I even pick a $w$ that is useful to the proof?

Answer 1

This is a very hard one to prove via the pumping lemma, as you have to construct a string that eventually gives you something of the form $0^{n}1^{n}$ for some $n$ when you pump it the right number of times. As Renato notes, your decomposition (at the time of writing this answer) is incorrect. We'll come back to this.

A simpler way is to use the closure properties of regular languages. In particular, regular languages are closed under complementation and intersection, so

1. If $R$ is regular, then $\overline{R} = \Sigma^{\ast}\setminus R$ is also regular.
2. If $R_{1}$ and $R_{2}$ are regular, then $R_{3} = R_{1} \cap R_{2}$ is also regular.

So we assume that $L = \{0^{m}1^{n} \mid m \neq n\}$ is regular. Then by (1), $\overline{L} = \Sigma^{\ast}\setminus L$ is regular. In particular note that $\overline{L}$ includes all strings of the form $0^{n}1^{n}$.

The language $A = \{0^{a}1^{b} \mid a,b \in \mathbb{N}\}$ is regular (we can show this via a regular expression, DFA or regular grammar for the language, e.g. $0^{\ast}1^{\ast}$).

Then by (2) $\overline{L}\cap A$ must also be regular, but this is the language $\{0^{n}1^{n}\}$, which is not regular (and much easier to prove via the pumping lemma!).

As noted in the question you linked however, it is possible to do it with the pumping lemma, but you need to pick your starting string carefully. As we only have two sections to the string, the obvious approach is to have a string of the form $0^{p}1^{x}$ for some $x$, so then we know that $y = 0^{k}$ for some $k\leq p$. Now the trick is to pick $x$ such that we can pump the string some number $y$ times and get $p + (y-1)\cdot k = x$. Of course we don't know what $k$ is - it could be anything from $1$ to $p$, so $x$ needs to take this into account. Hence $x$, in part, needs to (almost) be a multiple of every number from $1$ to $p$. So if we pick $x = p + p!$, we can say that for every $k$, there exists a $y$ such that $p + (y-1)\cdot k = p + p!$. In particular $y = \frac{p!}{k}+1$.

So then our starting string is $s=0^{p}1^{p+p!}$. By the pumping lemma if $L$ is regular, we can break $s$ up in $xyz$ such that $|y| \geq 1$, $|xy| \leq p$ and $xy^{i}z \in L$ for every $i \in \mathbb{N}$, but we have just shown that for $i = \frac{p!}{k}+1$, we get the string $0^{p+p!}1^{p+p!} \notin L$. Hence $L$ violates the pumping lemma, can thus can't be regular.

Answer 2

Thumbs down because your decomposition is wrong. Pumping lemma complies only if you choose a valid decomposition ($|xy|\leq p$ and $|y|\geq 1$). The idea is that you prove that there are no possible(valid) decompositions such that the pumping lemma is fulfilled