$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?

  • 2
    $\begingroup$ 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$. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Nice. You could even have eliminated everything but the first sentence of your third bulleted item. $\endgroup$ – Rick Decker Oct 23 '14 at 13:27
  • $\begingroup$ I wanted to avoid a question like "Why is $uv^2w$ not in $L$?" :) $\endgroup$ – Danny Oct 23 '14 at 13:32

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.