# How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?

I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular.

If the alphabet is $$\Sigma = \{a, b\}$$ and the language is $$L = \{a^{i + 1} b^{4i + 2} \mid i \in \mathbb N\}$$, how do I prove the language is not regular using pumping Lemma?

Also what is a pumping length, how do i know to assign a pumping length to the language stated above?

• You're essentially asking how pumping lemma proofs work. There are dozens of pumping lemma questions and solutions already in CS.stackexchange... some of which are really similar to this question. Is there a specific part of a sample solution that you can't adapt to this question? – JimN Sep 6 at 22:49
• Do you mean the language $\{a^mb^{4m+2} \mid m \in {\Bbb N}\}$? Your use of $+$ in the definition of $L$ is somewhat disturbing. – J.-E. Pin Sep 7 at 12:01

Since I see questions about the pumping lemma on this site quite often, I decided to write a bit of a longer answer hoping that it helps people "get" the PL rather than just treating it as a "plug-n-chug" tool given to us by the gods of math.

## Understanding the PL

I think the best way to go about it is to basically (re-)derive the lemma. The idea is that if some language $$L$$ is regular, then there exists some DFA $$A$$ such that $$A$$ recognizes $$L$$. Now say that $$A$$ has $$m$$ states and suppose that we have some $$w \in L$$ with of length $$n > m$$ (note that any infinite $$L$$ must contain such a word) and consider the run of $$A$$ on $$w$$.

As $$w$$ has more characters than $$A$$ has states, there must be some state $$q$$ which occurs at least twice in $$A$$'s run on $$w$$, i.e. if we draw out the run through the graphic representation of $$A$$ we find some loop. In more formal terms, this means that there must be some substring $$s$$ of $$w$$ -- so $$w$$ can be written as $$w = rst$$ where $$r$$ and $$t$$ are remaining parts of $$w$$ left and right of $$s$$ -- such that $$A$$ is in state $$q$$ on the both the first and last symbol of $$s$$.

At this point, we need to understand the D part of DFA: $$A$$ is deterministic, so given that we start from the initial state on any input of the form $$r\Sigma^\ast$$ (any string starting with the substring $$r$$) we will always end up at the state $$q$$ and similarly, starting from $$q$$ on the word $$s$$ we always end up at $$q$$ again and finally, starting on $$q$$ given the word $$t$$ we always end up at the same (accepting) state. I like to think of such deterministic machines as music boxes; if you start the at the same point they end up playing the same melody.

This means that we can now create new words which $$A$$ must also accept by making $$A$$ go into state $$q$$ and presenting it with $$t$$, and the easiest way to do so is by taking the known string $$r$$ to get it to the state $$q$$ initially, then repeating $$s$$ some $$k \geq 0$$ times (which, because we start at $$q$$ now) will always get us back to $$q$$ and then appending $$t$$ to make $$A$$ go into an accepting state. Hence these words are of the form $$w_k = rs^kt$$ for some $$k \geq 0$$.

Taking a step back, we have now basically argued that $$A$$ cannot distinguish between $$w$$ and $$w_k$$; the result of the computation will always be the same. This is the essence of how the pumping lemma works.

## Using the PL

To apply the pumping lemma we must now find such $$w$$ and $$k$$ where $$w \in L$$ and $$w_k \notin L$$. Usually one will not be able to give $$w$$ directly as the size of the automaton $$A$$ is unknown (in fact we are trying to argue that such an $$A$$ does not exist, so yeah). In most cases, this boils down to taking a "large" string in $$L$$ such that the middle part of said string is big enough for us to find some part that if repeated would give us the $$w_k$$ we need.

Let us get specific now. Our language is $$L = \{a^{i + 1} b^{4i + 2} \mid i \in \mathbb N\}$$. We assume that $$L$$ is regular and thus admits a DFA $$A$$ of size $$m$$. If we consider the string $$w = a^{10m + 1} b^{40m + 2} \in L$$, we find that a state repetition must already occur in the $$a$$-part of $$w$$ as $$a^{10m + 1}$$ has more symbols than $$A$$ has states. Hence there must be a decomposition $$w = rst$$ where $$r = a^{\ell}$$, $$s = a^k$$ and $$t = a^{10m + 1 - \ell - k} b^{40m + 2}$$ with $$0 \leq \ell < m$$ and $$0 < k \leq m$$ (Can you figure out why the bounds on these variables are this way? This is a good test to see if you are confident with the first part, I think).

If we now consider the word $$w_2 = rs^2t = a^\ell (a^k)^2 a^{10m + 1 - \ell - k} b^{40m + 2}$$ and unpack it to $$a^{m + k + 1} b^{40m + 2}$$ we see that $$w_2$$ is not in $$L$$. It follows that $$A$$ does not recognize $$L$$ as we assumed that $$A$$ accepts $$w \in L$$ and then argued that it must also accept $$w_2 \notin L$$. As the choice of $$A$$ was arbitrary we find that no DFA can recognize $$L$$, which means that $$L$$ is not regular.

Assume the language is regular, i.e., there is an automaton that recognize the language with a finite set of states. Therefore there are $$i \neq j$$ such that processing $$a^{i +1}$$ and $$a^{j + 1}$$ reach the same state X. Processing $$4i + 2$$ b's in state X always ends up in the same state Y. State Y must be accepting because $$a^{i + 1} b^{4i + 2}$$ is in the language. At the same time it must not be an accepting state, because $$a^{j+ 1} b^{4i + 2}$$ is not in the language when $$i \neq j$$. Contradiction, so the language is not regular.