# Pumping Lemma for $L=\{a^{2k} b^n b^k \mid k\ge0, n\ge0\}$

$L=\{a^{2k}b^nb^k\mid k\geq0, n\geq0\}$ over alphabet $\{a,b\}$

How do I prove that $L$ is not regular using Pumping Lemma? All the examples I've come across had same exponents all around, and I'm a bit confused how should I write this down.

Should I start with $w=\{a^pb^pb^p\mid p\leq k, p\leq n\}$ where $w$ is a subset of $L$, or how should this be tackled?

• You cannot start with your $w$ since it's a set rather than a word. A good starting word would be $a^{2k} b^k$ for an appropriate $k$. – Yuval Filmus Oct 23 '14 at 4:24

• Choose for example the word $x=a^{2k}b^{k}\in L$ ( with $|x|=3k\ge k$)
• Possible partitions of $x=uvw$ are $u=a^l,\;v=a^s,\;w=a^mb^{k}$ with $s\ge 1,\; l+s\le k$ and $l+s+m=2k$
• Now lets look at $uv^2w=a^{2k+s}b^k$ which is clearly not in $L$. If $s$ is odd, than the number of $a$'s is odd and therefore $uv^2w\notin L$. If otherwise $s$ is even, then the number of $b$'s would have to be larger than $(2k+s)/2$, which it is not ($k<(2k+s)/2)$. Therefore $uv^2w\notin L$ holds for each $s\ge 1$.
$\rightarrow$ $L$ is not regular.
• I wanted to avoid a question like "Why is $uv^2w$ not in $L$?" :) – Danny Oct 23 '14 at 13:32