1
$\begingroup$

I want to prove this language $L=\{a^nb^{n^2+n}:n\in\Bbb N\}$ to be nonregular by the pumping lemma. This is my attempt, is this a correct way of doing it?

Let's suppose $L$ is regular. Let $s = a^kb^{k^2+k}$ such that $k \geq 0$ as a pumping length. So we have $s \in L$ and $|s| \geq k$.

Then, by the pumping lemma, $\exists s = xyz$ such that

  1. $|xy| \leq k$,
  2. $|y| > 0$,
  3. $\forall i \in \mathbb{N}, xy^iz \in L$.

Since $|xy| \leq k$ and $|y| > 0$, then $x = a^\alpha$, $y = a^\beta (\beta > 0)$, $z = a^{k - \alpha - \beta}b^{k^2+k}$, so $xy^iz = a^{k + i \beta - \beta}b^{k^2+k}$

Now, $$xy^iz \in L \iff (k+i\beta-\beta)^2 + k = k^2+k \tag{E}$$

To complete the proof I need to find a way to remove $k$ from the equation, and find $i$ such that $xy^iz \notin L$, but the simplification of equation $(E)$ is not easy, so I did the following simple way:

Let $k = 1$, so $s = abb$, we have $|s| \geq 1$, now, as $|xy| \leq k=1$ and $|y| \geq 1$, that means $y =a$, so $xy^iz = a^ibb$, and so for $i=2$ $xy^iz \notin L$, thus, $L$ is not regular.

However, I am not sure of the last step. Is it OK to let $k=1$?

$\endgroup$
4
  • $\begingroup$ Why all these questions "proof X is irregular by the pumping lemma"? "Cannot be recognised by a finite state machine" seems so much easier and intuitive to me. $\endgroup$
    – gnasher729
    Dec 21, 2022 at 10:03
  • $\begingroup$ Yes, the issue in that statement "cannot be recognized by a finite state machine"! How can you prove that?! $\endgroup$
    – Papa
    Dec 21, 2022 at 10:33
  • $\begingroup$ Very easy: After parsing a^n b and a^n' b, n ≠ n', we must end in two different states, since a following b^(n^2+n-1) in the first state. must end in an accepting state, and in the second state must end in a non accepting state. Infinite number of n's, therefore no finite state machine. $\endgroup$
    – gnasher729
    Dec 21, 2022 at 11:30
  • $\begingroup$ Perfectly fine as well! Thanks $\endgroup$
    – Papa
    Dec 21, 2022 at 11:33

2 Answers 2

0
$\begingroup$

Your proof is not correct when you "let $k=1$". You cannot choose the pumping length $k$ when you are using the pumping lemma to prove a language is not regular. For example, your proof does not exclude the possibility that $L$ could be regular with pumping length $2$.

Using the pumping lemma method to prove a language $L$ is nonregular is a turn-based game against an adversary:

  1. The adversary chooses an integer $p$.
  2. You come up with a word $w \in L$ of length at least $p$.
  3. The adversary splits the word into $w = xyz$, where $|xy| \leq p$ and $|y| \geq 1$.
  4. If you come up with an integer $i$ such that $xy^iz \notin L$, you win.

If it can be demonstrated that you can win this game no matter what the adversary does, then $L$ is not regular.

Let me show how you can always win the game.

  1. The adversary chooses $p$.
  2. You come up with $w=a^pb^{p^2+p}\in L$.
  3. The adversary split the word into $xyz$, where $|xy|\le p$ and $|y|\ge1$.
  4. You come up with $xy^2z$.
    $|xy^2z|=|w| + |y|= p^2+2p+|y|$, where $1\le|y|\le|xy|\le p$.
    Since the length of $xy^2z$ is strictly between the lengths of two adjacent words, $a^pb^{p^2+p}$ and $a^{p+1}b^{(p+1)^2+(p+1)}$ in $L$, $ xy^2z\notin L$.

You have won the game.


Here is another way that uses string homomorphism and Myhill–Nerode theorem instead.

Assume $L$ is regular. Let $\sigma$ be the string homomorphism such that $\sigma(a)=\epsilon$ and $\sigma(b)=b$. Then $\sigma(L)=\{b^{n^2+n}:n\in\Bbb N\}$ is regular, too.

However, for any $0\le i<j$,

  • $b^{i^2+i}b^{2(i+1)}=b^{(i+1)^2+(i+1)}\in L,$
  • $b^{j^2+j}b^{2(i+1)}=b^{(j+1)^2+(j+1)- 2(j-i)}\notin L.$

That is, each one of all infinitely many words of form $b^{i^2+i}$ belongs to a different Myhill–Nerode class w.r.t. to $\sigma(L)$. Myhill–Nerode theorem tells us that $\sigma(L)$ is not regular. This is a contradiction.

$\endgroup$
2
  • $\begingroup$ I have to say, that pumping lemma argument $4.$ is very nice. Usually that technique is used in $a^{2^n}$ and $a^{n^2}$, and I didn't pay attention. Thank you! $\endgroup$
    – Papa
    Dec 21, 2022 at 7:39
  • $\begingroup$ You are welcome. $\endgroup$
    – John L.
    Dec 21, 2022 at 7:41
0
$\begingroup$

The general pumping lemma tells us that any language L' which is a set of substrings of strings in L must fulfil the pumping lemma for L to be regular (L' need not be regular but must fulfil the pumping lemma). Every string $a^n b^n$ is a substring of a string in L, the language L' = $a^n b^n$ has often been proved irregular because it doesn't fulfil the pumping lemma, therefore L is not regular.

(Careful: We don't prove that L' is irregular. We prove that it doesn't fulfil the pumping lemma. So L' being irregular proves nothing, it is the fact that the pumping lemma doesn't apply to L' which proves that L is not regular).

(Note: The proof for the general pumping level is basically the same as for the normal pumping lemma).

General rule: If for every n ≥ 0 $a^n b^n$ is a substring of some string in L, then L is not regular.

$\endgroup$
4
  • $\begingroup$ Nice nuanced point $\endgroup$
    – Papa
    Dec 21, 2022 at 11:44
  • $\begingroup$ @gnasher729 I am afraid the "General rule" is wrong. For every $n\ge0$, $a^nb^n$ is a substring of some string in $\Sigma^*$. However, $\Sigma^*$ is regular. Another counterexample is $\{a^ib^j: i,j\in\Bbb N\}$. $\endgroup$
    – John L.
    Dec 21, 2022 at 17:43
  • $\begingroup$ @user1125632 FYI just in case, "the general pumping lemma" is described here on Wikipedia. $\endgroup$
    – John L.
    Dec 21, 2022 at 17:45
  • $\begingroup$ Thank you John, can you please try to answer some other questions I posted? $\endgroup$
    – Papa
    Dec 21, 2022 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.