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$.

  • 3
    $\begingroup$ 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!). $\endgroup$ Nov 11 '17 at 8:37

Some people can be absolutely sure, and at the same time absolutely wrong. In this case, you are one of those people.

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$.

  • $\begingroup$ "A language is a set of strings. A language is not the rules that were used to express the language." +1 $\endgroup$ Nov 11 '17 at 14:51

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$.

More generally, when we are not sure about something in mathematics, we try to prove it. You claim that the language is not regular, but you don't have any argument. Your friends claim that their language is regular, and they do have an argument. If their argument is valid, then the only conclusion is that the language is regular.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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