0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – JimN Sep 6 at 22:49
  • $\begingroup$ 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. $\endgroup$ – J.-E. Pin Sep 7 at 12:01
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy