I've been working on understanding the Pumping Lemma for 2 days now and I feel like I may have finally got somewhere. I was hoping to show you guys a question and my working out and if you think i'm on the right lines that would be great and if not, any help would be extremely appreciated.

The question I have been asked is this:

Use the Pumping Lemma to determine whether the language L = {a^n b^2n | n >= 1} is regular or not.

My answer:

I chose a pumping length 'm'.

Word chosen = a^m b^2m as it is certainly longer than m.

w = xyz
a^m b^2m = xyz

y!= empty and |xy| <= m

So the max length of xy is a^m.

y = a^k where 0 < k <= m
as y cannot be empty but could possibly be length m as x can be empty.

x = a^q where 0 <= q < m

as q can be empty but cannot be equal to m as y cannot be empty.

z = a^m-k-q b^2m

as z can hold any remaining a's and all the b's.

Therefore xyz = a^q a^k a^m-k-q b^2m => a^m a^2m so the language is regular.

PS I don't expect you to do the question yourself, but reading over my answer to see where i'm going wrong (if so) would be great as I assume some of you are quite familiar with the pumping lemma more than I.

  • $\begingroup$ The pumping lemma says that a regular language satisfies the "pumping property". Showing that a particular language satisfies the pumping property does not show that the language is regular; however, if you can show that a language does not satisfy the pumping property, that implies the language is not regular. I.e. you cannot use the pumping lemma to show that a language is regular, only to show that it is not regular. $\endgroup$ May 10 '15 at 18:53
  • $\begingroup$ Thanks for the response, yes I'm basically using the pumping lemma to see if the that language does not satisfy the pumping property. If it does, then it is implied that the language is not regular. I'm very new to formal language theory and have been struggling as the textbooks make pumping lemma very confusing. In this case, the language does satisfy the pumping lemma from my working out, but I may be wrong $\endgroup$ May 10 '15 at 18:56
  • $\begingroup$ Given that you are being asked to use the pumping lemma to determine whether the language is regular, this strongly suggests that the language does not have the pumping property, and is therefore not regular (that is the only way this question is even answerable). I suggest working along those lines. $\endgroup$ May 10 '15 at 18:58

You're close here, but you are missing a key idea of the pumping lemma. The lemma works because for any word in the language that is over a certain 'pumping length' $m$, if we imagine an automata for that language, at some point the language must re-enter a state it has already visited.

i.e.$\;\; s \overset{x}{\rightarrow} q \overset{y}{\rightarrow} q \overset{z}{\rightarrow} f$ where $s$ is the start state, $q$ is a middle state, $f$ is an accept state and $\overset{a}{\rightarrow}$ represents some series of transitions. Since we have $q\overset{y}{\rightarrow}q$, we can repeat this as many (or as few) times as we want and so this new word should also be accepted by the automata and so recognised by the language.

i.e. $\;\; s \overset{x}{\rightarrow} q \overset{y}{\rightarrow} ...\overset{y}{\rightarrow}q \overset{z}{\rightarrow} f$

so for any word $w=xyz$, such that $s\geq m$, $|xy| \leq m$ and $|y|>0$, it should hold that any word $xy^iz\; |\; i\geq 0$ is accepted by the language

Your proof is correct up until your final statement:

"Therefore $xyz = a^q a^k a^{m-k-q} b^{2m} => a^m a^{2m}$ so the language is regular."

While your thinking is correct, this does not mean the language is regular. If the language is regular, for every word in that language we must have $xy^iz$ in the form $a^ma^{2m}$ for every $i\geq 0$. This means that from the pumping lemma, we cannot say definitively that a language is regular, because we cannot check every $xy^iz$ for every possible word in the language.

We can, however show that a language is not regular, if it doesn't satisfy the pumping lemma i.e. there is some $i\geq 0$ such that $xy^iz$ is not in the correct form (in this case $a^ma^{2m}$). For this example, let's check $xy^2z$:

$xy^2z = a^qa^{2k}a^{m-k-q}b^{2m} = a^ka^mb^{2m} = a^{m+k}b^{2m}$ which is clearly not in the form $a^mb^{2m}$.

So we have found an example showing that the pumping lemma does not hold for this language, therefore this language is not regular.

It should also be noted that a language is regular iff there is a regular expression (or equivalent finite automata) that represents it. This means the easiest way to prove a language is regular often is to construct a DFA or NFA that accepts the language. As an exercise, try to construct a DFA or NFA for the language you asked about. You should find that it isn't possible because the language is not regular.


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.