I'm having trouble understanding Pumping Lemma for $RL$ , i know that $0^{2n}$ is regular and we can design a FSM for it.
Here's my pumping Lemma statement

Let $p$ be the pumping length and my string is $0^{2p}$
1. $z=|0^{2p}|=> 2p > p $ (Satisfied)
2. $z=uvw$ such that $|uv|\geq p$, I'm choosing $|u|=n-p$ and $|v|=p$ so that $|uv|\geq p$ (Satisfied)
3.Now $u(v^i)w$, I choose $i=3$ then $|uvw|=2(n+p)$ which is even
But if $n=2$ then $|uvw|=2n+p$, how do i know if this could be even/odd?

  • 2
    $\begingroup$ You don't get to choose the partition $z = uvw$. The pumping lemma only guarantees that such a partition exists. $\endgroup$ – Yuval Filmus Aug 23 '17 at 8:25
  • 3
    $\begingroup$ Haven't we had this or very similar languages a lot recently? $\endgroup$ – Raphael Aug 23 '17 at 11:32
  • 1
    $\begingroup$ Title says "...not Regular using Pumping Lemma", the body text says "...i know that $0^{2n}$ is regular...", the question is not clear. $\endgroup$ – fade2black Aug 23 '17 at 14:09
  • $\begingroup$ @fade what I meant was we could prove it is not regular but actually it is regular $\endgroup$ – user2643191 Aug 23 '17 at 14:17
  • 2
    $\begingroup$ Okay, I see your point. Please have a look at this almost identical question if it helps. $\endgroup$ – fade2black Aug 23 '17 at 14:28

You can't prove that a language is regular by applying the pumping lemma.

Regular Languages are a subset of Languages that satisfy the pumping lemma. So you can only proof irregularity with the lemma. (By assuming that the language is regular and coming to a contradiction)

One way to show that a language is regular, is e.g. constructing a Regular Expression, NFA or DFA (all of these being equivalent).

| cite | improve this answer | |
  • $\begingroup$ There are other ways of proving that a language is regular, for example using closure properties. $\endgroup$ – Yuval Filmus Aug 24 '17 at 8:41
  • $\begingroup$ @YuvalFilmus thank you, I edited my answer. $\endgroup$ – KillPinguin Aug 24 '17 at 8:46

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