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.
Best Answer
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:
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.