0
$\begingroup$

I have the following language...

$$A=\{a^ib^i | i>0\}\cup\{a^jb^k|j>2, k>3\}$$

Now, pumping lemma states that a regular language can be written in the form $x=pq^ir$. What confuses me is how to split the language into three parts, this is my attempt:

$p=a^j$

$q=a^jb^k$

$r=b^k$

I believe my attempt is incorrect but this is the extent of my knowledge on the subject. Can someone explain how to split the language properly?

$\endgroup$
2
$\begingroup$

The mistake is in what you're attempting to split. The pumping lemma says if $L$ is a regular language, there exists a number $m$ (the pumping length) such that every string $x \in L$ can be be split into three parts, $x=pqr$ such that:

  1. $|pq| \leq m$
  2. $|q| \geq 1$
  3. $pq^{i}r \in L$ for all $i \in \mathbb{N}$

So it's the strings in the language that can be split and pumped, not the language.

So for the language you give, which is regular, you should be able to take any string, split it and pump it. One problem with doing this in practice is that the pumping length $m$ is not typically known, however we can take a larger example here and we don't have to worry.

Consider the string $y = a^{2m+3}b^{4}$, then we know that $pq = a^k$ for some $k \in [1,m]$, and in particular $p = a^{k_{1}}$ with $k_{1} \in [0,m-1]$, $q = a^{k_{2}}$ with $k_{2} \in [1,m]$ and $k_{1}+k_{2}=k$. Then $r = a^{2m+3-k}b^{4}$. As $k \leq m$, this string is in the language $A$ (it fits the definition in the second part).

Now we get to the pumping part; as $A$ is regular, assuming that we've split things correctly, we should be able to pump $y$. If we pump down, we get $a^{2m+3-k_{2}}b^{4}$, which is still in $A$ (again, $k_{2} \leq k \leq m$). If we pump up $n$ times, we get $a^{2m+3+nk_{2}}b^{4}$, which still fits the definition and is in $A$.

Then as $A$ is regular, we should be able to do this for every string in the language, but there's no real reason we would want to as it doesn't tell us anything - there are non-regular languages which can still be pumped (e.g. see the wikipedia article). What we use the pumping lemma for is showing that languages are not regular by showing that the language we suspect is not regular contains at least one string that cannot be broken up and pumped in any way.

$\endgroup$
  • $\begingroup$ I found this to be very helpful, but could you clarify one thing? Is there a specific reason why you chose $a^(2m+3)$? Could it have been anything else? For example $a^(4m+3)$? $\endgroup$ – Bolboa Feb 3 '15 at 1:32
  • $\begingroup$ @Bolboa, yes, it could've been anything (as long as the string was in $A$), it was just convenient because it doesn't require any careful arguments to say that the pumped versions are still in $A$. $\endgroup$ – Luke Mathieson Feb 3 '15 at 1:34

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.