0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Harshal Carpenter Oct 22 '14 at 19:47
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 22 '14 at 19:49
  • $\begingroup$ @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. $\endgroup$ – Harshal Carpenter Oct 22 '14 at 19:54
  • $\begingroup$ @HarshalCarpenter Every finite language is regular, for example it can be written as a regular expression. Your proof will fail since the pumping length $p$ would be too big. You can't choose $n = p$ if $n \geq 10000$. $\endgroup$ – Yuval Filmus Oct 22 '14 at 19:56
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Oct 22 '14 at 20:05

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.