If you want to make money online : Register now

[Solved]: Pumping Lemma confusion

, , No Comments
Problem Detail: 

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?

Asked By : Bolboa

Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37908

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback