I've been watching lectures from Coderisland on YouTube about finite state machines, DFAs and NFAs, and in one discussion he talks about how to use the pumping lemma to show how a language is not regular. I don't know quite how to apply the lemma and want to understand if I'm doing it right. If I had something like:

w = {anbk, n =/= k}

am I correct in that I can say that:

h = {anbn + r, r > 0} is a subset of w, and thus if I show by the lemma that h is not regular, that w must not be regular since h is a subset of w.

The way I would show this is as follows:

  1. h = xyz
  2. |xy| <= n
  3. x = an-r
  4. y = ar
  5. z = bn + r
  6. xyz = an-rarbn + r
  7. xy2z = an-ra2rbn + r = an + rbn + r

Thus h cannot be regular since an + rbn + r is not of the form {anbn + r, r > 0}, and since h is not regular w must not be regular, since h is an element of w.

Have I applied it correctly? I understand how to apply it for an easy language like {anbn}, because I can apply the lemma directly to this language, but the only way I could think of for my language was to create a subset that belongs to my language, and apply the lemma to that.

If I haven't applied it correctly, is there a way to show that my language is not regular (or regular), using another lemma, or perhaps with closure properties?

This is a really awesome topic, even if I don't understand the pumping lemma fully, I'm excited to explore it further!

  • $\begingroup$ Please note our reference question that covers this in-depth. Note also that you can use MathJax to typset mathematics. $\endgroup$
    – Raphael
    Jan 26 '14 at 11:37

A subset of a regular language could be non-regular, so the entire line of reasoning is flawed. As an example, every non-regular language over $\{0,1\}$ is a subset of the regular language $(0+1)^*$.

Regarding the language $H$, you'd do better writing your proof in paragraph-style rather than as a cryptic list. In addition, you made the following mistakes:

  1. You never mention which $h$ you take.
  2. You don't get to choose the decomposition $h = xyz$. The proof has to work for every such decomposition satisfying the properties given in the lemma ($|xy| \leq n$, where $n$ is the "pumping constant").

Several ways of showing that your original language is not regular are given in this answer.


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.