# Pumping Lemma for Regular Language (Is my answer correct)?

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.

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.

• 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. May 10 '15 at 18:53
• 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 May 10 '15 at 18:56
• 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. 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

"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}$.