Why can't this be a Regular Language?

Question

Given $L$ - the language consisting of all the strings of the form $\{0^n 1 ^m\}$ where $m < n$.

How can I prove that $L$ is not a regular language?

Answer 1

You use the Pumping Lemma. Suppose $L$ were regular. Let $p$ be the pumping length. Then we can write each $w \in L$ as $w = xyz$ for $|y| \geq 1$, $|xy| \leq p$ and have $xy^{i}z \in L$ for each $i \in \mathbb{N} \cup \{0\}$.

So let $w = 0^{n}1^{m}$ with $(n + m) \geq p$ and $n \geq m + 1$. So now there is no choice for $y$, since choosing $y = 1$ will obviously allow for $0^{k}b^{j}$ with $j > k$. If we choose $y = 0$, then we can remove a $0$ from the string since $i = 0$ is a valid exponent by the pumping lemma. And so if $y = 0$, then we have a choice where $0^{n}1^{n} \in L$ by the Pumping Lemma, which contradicts the definition of $L$.

Answer 2

The Myhill-Nerode theorem handles this easily:

The infinitely many prefixes $\mathtt 0^n$ ($n \ge 1$) are all distinguishable.

Namely, if $n<k$, then $\mathtt 0^n$ and $\mathtt 0^k$ are distinguished by $\mathtt 1^{k-1}$. More precisely $\mathtt 0^n\mathtt 1^{k-1}\notin L$ (because $k-1\ge n$), whereas $\mathtt 0^k\mathtt 1^{k-1}\in L$.

Since there is an infinity of pairwise distinguishable prefixes, the language is not regular.