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

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

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

1. Let $0^p 1^{5p}$ be 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 $L$, thus not a regular language.

But how to prove for condition $\{0^n 1^{5n} \mid 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.

The condition $n>10\,000$ makes no real difference. If the pumping length is greater than $10\,000$, your existing proof works. If the pumping length is $10\,000$ or less, then pumping the string $0^{10\,000}1^{50\,000}$ gives you a string that isn't in the language because it has too many zeroes.
• or can we say that as $n \gt 10,000$ is not a regular language then complement of it $n \le 10,000$ is also not regular ? – Harshal Carpenter Oct 22 '14 at 19:47
• Not quite. Actually, $\{0^n 1^{5n} : n < 10000 \}$ is regular, being a finite language. You can use this argument the other way around: had $\{0^n 1^{5n} : n \geq 10000 \}$ been regular, so would $\{0^n 1^{5n} : n \geq 0\}$ since the union of two regular languages is regular. – Yuval Filmus Oct 22 '14 at 19:49
• @YuvalFilmus How is $( 0^n 1^{5n} : n < 10,000 )$ regular? Lets say $n = p$ then for $0^p 1^{5p}$, pumping the $y$ will get us a string not in the language. – Harshal Carpenter Oct 22 '14 at 19:54
• @HarshalCarpenter The pumping lemma says "There exists a $p$ such that, for every string in the language longer than $p$, blah blah blah". For a finite language, we can just choose any $p$ bigger than the longest string in the language and, bingo!, the requirement that every string longer than $p$ has some property is vacuously true. – David Richerby Oct 22 '14 at 20:05
• @HarshalCarpenter Not quite. The complement of $\{0^n 1^{5n} \mid n < 10000\}$ consists of $\{0^n 1^{5n} \mid n \geq 10000\}$ as well as all strings which are not of the form $0^n1^{5n}$ at all. – Yuval Filmus Oct 22 '14 at 20:06