Prove if $L = \{0^m1^n \mid m \neq n\}$ is regular or not

Question

I am trying to show whether this language is regular or not:

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

Since I cannot create or think of an automaton that recognizes $L$, I am suspecting that $L$ is not regular. From the book I am using, it seems I can use the pumping lemma, I have done this:

Let $p$ be the pumping lemma constant, and let $w=0^p1^{p+1}$

In this case $$|w|=2p + 1\geq p$$

We can divide $w$ into $xyz$, where $x=0^{p-1}$, $y=0$, $z=^{p+1}$, then $|y|\geq 1$

If L was regular, then $\forall k \geq 0, xy^kz \in L$. Let choose $k=2$, then:

$$xyyz=0^{p-1}001^{p+1}=0^{p+1}1^{p+1}$$

Here is where I am stuck, how do I prove that $L$ is not regular?

Another question, pumping lemma applies only to infinite languages?

Answer 1

You don't need to invoke the PL directly here. Instead, we'll do a proof by contradiction. Suppose $L$ was regular, then, since regular languages are closed under complement, $\overline{L}$ is regular (where the overbar represents complement), and since regular languages are closed under intersection, $\overline{L}\cap 0^*1^*$ would be regular (where the regular expression denotes the language $0^*1^*=\{0^n1^m\mid n,m\ge 0\}$), but $\overline{L}\cap0^*1^*=\{0^n1^n\mid n\ge 0\}$, which you likely know is not regular, establishing the contradiction we needed. Thus your language isn't regular.

In answer to your other question, the PL generally applies only to infinite languages since you don't know what the PL integer $p$ is, so absent other information, you need an infinite language to be sure that there is some string of length $\ge p$ in the language, regardless of how large $p$ is.

Answer 2

It's not so evident, but you can also apply the PL directly:

• let $p$ be the pumping length
• pick $w = 0^p 1^{p + p!}$

Clearly $w \in L$

The pumping lemma says that $w = xyz$ with $|xy| \leq p, |y| \geq 1$, so we have that $y$ must be "made of" $0$s; suppose that $y = 0^a\;, 0< a \leq p$; then by the PL we have:

$$xyz = 0^{p-a} 0^{ai} 1^{p +p!} \in L\quad \text{ for all } i \geq 0$$

It's enough to pick: $i = (1+p!/a)$ and you get:

$$xyz = 0^{p-a} 0^{a(1+p!/a)} 1^{p +p!} = 0^{p-a} 0^a 0^{a (p! /a) }1 ^{p + p!} = 0^{p+p!}1^{p+p!} \notin L$$

(just note that $p! / a$ is an integer because $0<a\leq p$)

Answer 3

The pumping lemma applies to all languages. Let $L$ be a finite language. The pumping lemma says that, for some $p$, every string in $L$ that is longer than $p$ can be written as blah, blah, blah. Since $L$ is finite, every string in it has length at most $\ell$ for some $\ell$. So just take $p>\ell$ and the requirements of the pumping lemma are vacuous: $L$ has no strings of length greater than $p$, so there are no counterexamples to the claim that every string of length greater than $p$ can be written as blah, blah, blah.

Answer 4

Other answers have already mentioned about pumping lemma and Myhill-Nerode theorem. Through which you could prove that a DFA does not exists to accept the given language, hence it can't be regular.

One quicker way (not actually a formal proof) to check whether a language is regular or not is to see if your DFA has to count infinitely in order to recognise the language, then it is not regular.

For $L=\{0^m1^n \mid m \ne n\}$, the DFA has to count the number of 0s and then count the number of 1s. If they are equal then reject it otherwise accept the string. Here with no upper bound on m, it could be infinitely large and the DFA can't keep track of m. So it is not a regular language.

Is $L=\{0^m1^n \mid m \ne n, 0 \le m \le 2\}$ regular? Here $m$ has an upper bound. The DFA could count up to $m$ and then see if it is equal to $n$ or not. We could have a DFA accepting for regular expression $(1^+)+(0+011^+)+(00+001+00111^+)$

Is $L=\{0^m1^n \mid m \ge 0, n \ge 0\}$ regular? Here the DFA does not even need to count anything. The regex would be $(0^*1^*)$

Answer 5

You can also use Myhill–Nerode theory.

Consider a DFA accepting your language, and let $q_i$ be the state that the DFA is in after reading $0^i$. I claim that $q_i \neq q_j$ whenever $i \neq j$, which is impossible since a DFA only has finitely many states. Indeed, if $q_i$ were equal to $q_j$, consider the state that the DFA is in when starting at $q_i$ and reading $1^i$. Since $0^i1^i \notin L$, it should be a rejecting state, but since $0^j1^i \in L$, it should be an accepting state – and we have reached a contradiction, showing that the assumption $q_i = q_j$ must be wrong.

Answer 6

You have almost proved the language is not regular using Pumping Lemma,

In the last step where you pump up the string you get

$$xy^2z = xyyz=0^{p-1}001^{p+1}$$ $$=0^{p+1}1^{p+1}$$

which does not belong to the language L, this contradicts your assumption that the language is regular, So the Given language is not regular.