# Pumping Lemma for irregular language, how to choose and divide the string

The language on the alphabet $\{a,b\}$ is $$L=\{ab^nab^{n+1} |n>0\}$$

so i have to take a string w = xyz:

what's the best string to choose such that $|w| > n$? and then what about the division?

like $w=ab^nab^{n+1}$ is a correct option? Then how can I divide this into three pieces? My attempt:

$x = ab^s$ with $0 ≤ s ≤ n -1$

$y= b^ta$ with $0 < t ≤ n - t$

$z = b^k$ with $0 ≤ k < n - t - s$

• You don't get to choose how to divide the string! You have to consider all possible divisions. – Yuval Filmus Jan 25 '17 at 21:10
• Yes but I can choose the string to divide, important is that it still belongs to the languages and that it is $> n$. Right? – emaph Jan 25 '17 at 21:15
• You really don't have much choice regarding the string $w$. It will have to be $ab^nab^{n+1}$ for large enough $n$. – Yuval Filmus Jan 25 '17 at 21:17
• Ok I got this. Then what about the division? – emaph Jan 25 '17 at 21:29
• What about it? You have to consider all possible ways. I suggest taking a look at some worked-out examples. You can find many on the web. If you're still lost after that, I suggest asking your TA. – Yuval Filmus Jan 25 '17 at 21:30

w = abn-1abn.

We have to consider all the division xyz = w with |y| >= 1 and |xy| <= n. So

x = apbr

y = aqbs

z = btabn

where:

• p + q = 1
• r > 0 implies p = 1
• q + s > 0
• r + s + t = n - 1

Let's now consider w' = xy0z=apbr+tabn. If x is the empty string, then w' is missing the initial 'a' (and maybe some b), so w' is not in L. Else if x is not empty, we know that y contains at least one occurrence of 'b', so w' can't be in the form abnabn+1 and w' is not in L.

• I got your process, even if probably I would have never managed to think about this solution. Thanks! – emaph Jan 26 '17 at 18:46