How to prove that $ \{ 0^n 1^{5n} : n \ge 10000 \} $ is not a regular language?

Question

I proved that $$ \{0^n 1^{5n} : n \ge 0\} $$ is not a regular language using Pumping Lemma by following way.

Solve by contradiction that $ L = \{ 0^n 1^{5n} : n >= 0 \}$ is regular language.

1. Let $0^p 1^{5p}$ is in L, where p is the pumping length.

2. Now here if the language L is regular language, $0^p 1^{5p}$ can be represented in the form xyz where $|xy| \le p$ & $|y|\gt0$.

3. Thus, from step 2, we can say that $xy = 0^p$ and $y = 0^j$.

4. So, $xyz = (0^{p-j})(0^j)(1^{5p})$.

5. Now pumping the value of $y$ to $2$, $xyyz = (0^{p-j})(0^j)(0^j)(1^{5p}) = (0^{p+j})(1^{5p})$, which is surely not in the L, thus not a regular language.

But how to prove for condition $ \{ 0^n 1^{5n} : n \ge 10000 \}$ & for also $n \le 10000$, we can just prove that one of them is not regular and obviously by rules the complement will also be not regular.

Answer 1

There is a small correction to be made in part 3 of your proof. The string can be divided in may ways, $xy$ is not necessarily $0^{p}$ but it is true that the string $xy$ consists of only zeroes, so $y$ consists of only zeroes. That could also be just one zero, for instance. The 'unused' zeroes end up in z. But for whatever number of zeroes $y$ has, pumping it will result in generating at least some strings that are not in $L$ because they have a number of zeroes that is not $1/5$ of the number of 1's.

The complement of $L = \{0^{n}1^{5n}$ $|$ $n \geq 10000\}$ is not $\{0^{n}1^{5n}$ $|$ $n \leq 10000\}$. The complement is also not $\{0^{n}1^{5n}$ $|$ $n < 10000\}$. The complement of a language is generated by taking the same alphabet, and generating all strings that are not in that language.

Thus, for instance the string 00 is in the complement of $L$. And the string 1111. And the string $0^{10000}1^{10000}$.

You can prove that $L$ is not regular by showing there exists a string in $L$ that cannot be pumped. Such a string is for instance (again!) $0^{p}1^{5p}$. The argument goes as you showed, because again $y$ is just zeroes, and after pumping you could end up with strings that have more 0's than $1/5$ of the 1's.

Now the funny thing is that $\{0^{n}1^{5n}$ $|$ $0 < n \leq 10000\}$ (I avoided a negative $n$) is actually a regular language. This can be proven by constructing a regular expression that recognizes the language. Maybe there is a shorter way, but a simple way to consider this is just writing out all possibilities:

$\epsilon \cup 011111$ $\cup$ $000001111111111111111111111111$ $\cup ...$

This is possible because since there is a maximum value for $n$, all possible strings in the language can be written out. If there would be infinitely many strings in the language, you can not do this.

Answer 2

The language $L_- = \{0^n1^{5n} \mid 0 \leqslant n \leqslant 10000 \}$ is finite and hence is regular. Suppose now that the language $$ L_+ = \{0^n1^{5n} \mid n \geqslant 10000\} $$ is regular. Since regular languages are closed under union, $L = L_+ \cup L_-$ would be regular. Since you already proved that $L$ is not regular, it follows that $L_+$ is not regular.