# Is the language $\{ 0^m 0^n : 0 \leq m \leq n\}$ regular?

Is the following language regular? $$\{ 0^m0^n : 0\le m\le n \}.$$

According to me, it is not regular. However, some of my friends are arguing that every string in $0^*$ can be divided into $0^m0^n$ satisfying the constrains between $m$ and $n$, hence it is regular.

Although I am absolutely sure that their reasoning is false, they are thinking in reverse, I would like a third opinion.

Here is my proof of non-regularity:

Let us take $0^p0^{p+1}$ as a string.

Applying the pumping lemma, we find that the part with $0^p$ needs to be pumped. So, even if it is pumped by one 0 at a time, we will soon get $0^{p+2}0^{p+1}$, which violates the constraints between $m$ and $n$.

• Your suggested proof doesn't work. You haven't explained why "the part with $0^p$ needs to be pumped". Moreover, the word $0^{p+2} 0^{p+1}$ doesn't violate the constraints, since it is also equal to $0^{p+1} 0^{p+2}$ or to $0^0 0^{2p+3}$, both of which don't violate them (and there are even some others!). Nov 11 '17 at 8:37

A language is a set of strings. A language is not the rules that were used to express the language. $0^*$ and $\{0^m 0^n: 0 ≤ m ≤ n\}$ are the same language, even when that language is expressed in two different ways. And $0^*$ and $\{0^m 0^n: m ≥ n ≥ 0\}$ is again the exact same language, just expressed differently.
Your attempted "pumping lemma" proof fails for the same reason: For example, $0^5 0^4$ is in the language, because it is exactly the same string as $000000000$, which is again the exact same string as $0^0 0^9$.
Your language is the same as $0^*$ (and so, regular), since you can always choose $m = 0$. More formally, clearly your language is a subset of $0^*$. Conversely, for any $n$, your language contains $0^n$ since $0^n = 0^0 0^n$ and $0 \leq 0 \leq n$.