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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
8
  • $\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
    Commented Oct 22, 2014 at 19:47
  • 1
    $\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
    Commented Oct 22, 2014 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
    Commented Oct 22, 2014 at 19:54
  • 2
    $\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
    Commented Oct 22, 2014 at 20:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – Yuval Filmus
    Commented Oct 22, 2014 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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