I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using the pumping lemma (even though I know it applies with our choice of string, since the string is at least $n$ long).


To apply the pumping lemma for regular languages:

  1. You assume some pumping length $p > 0$: Suppose a pumping length $p$.
  2. You pick a string $s$ such that $|s| \geq n$: Indeed, $a^pb^p$ is a good one since $|a^pb^p| = 2p \geq p$.
  3. Now, you have to consider all the partitions of $s$ as $xyz$, such that
    1. $|y|>0$ and
    2. $|xy| \leq p$.

In this case, the 2nd inequality restricts $y$ to contain only $a$'s. Therefore, all the possible partitions are of the form $y = a^k$, $x = a^{p-k-r}$ and $z = a^rb^p$ for $k$ and $r$ such that $k > 0$ and $p \geq k + r$.

  1. For every possible partition of the previous step, you have to show that there is some $i\in\mathbb{N}$ such that $xy^iz$ is not in the language.

Here, consider $i = 0$. Then $xy^0z = xz = a^{p-k-r}a^rb^p = a^{p-k}b^p$. It is now a matter of showing that $p-k\neq p$, or, equivalently, that $k > 0$ which is already true.

  • $\begingroup$ Apologies for the late response, I just wanted to say thank you! Your response helped my understanding a lot! $\endgroup$ – James Ronald Mar 2 '20 at 15:11

In this particular case, you can use the pumping lemma with any word of length at least $p$ (the pumping length). Indeed, consider any word $w = a^nb^n$, and suppose that we are given some decomposition $w = xyz$ where $y$ is non-empty and $xy^tz \in \{ a^ib^i \mid i \geq 0 \}$ for all $t$ (we don't even need the bound on $|xy|$). If $y$ consists only of $a$'s, then $xy^2z$ will have more $a$'s than $b$'s; if it consists only of $b$'s, then $xy^2z$ will have more $b$'s than $a$'s; and if it consists of both, then $xy^2z \notin a^*b^*$.

If instead of your language we consider the language of all words with equally many $a$'s and $b$'s (but not necessarily in the format $a^*b^*$) then the above argument would fail, and you would have tobe more careful when choosing your word; however, $a^pb^p$ would still work.


Your Answer

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

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