# Show that $a^k w b^k$ when $|w|_a$ is divisible by $3$ is not regular

I want to show that $L = \{ a^k w b^k \mid k \geq 0, w \in \{a,b\}^*, |w|_a \text{is divisible by } 3 \}$ is not regular.

I tried to use Pumping lemma as follows: Let $p$ be pumping length. $a^pb^p \in L$. By pumping lemma, then $a^{p+k}b^p$ is in $L$ too. If $k$ is not divisible by 3, then we have a contradiction. If $k$ is divisible by 3, then $(k-1)$ is not. String $a^{p-1}b^{p-1} \in L$, then, I thought, by pumping lemma $a^{p-1-(k-1)}(a^{k-1}b^1)(b^{p-1})$. But then I realised that the number of letters I can pump is different in that case (since the first $p$ letters are different).

So, now I am quite lost, any advice is appreciated. Thanks.

-
You might want to explain the $\vdots$ notation since that's not standard. – Ted Feb 25 '12 at 17:48
@Ted, sorry, I didn't realize that it's not a common notation. I've updated the post. – Daniil Feb 25 '12 at 18:31
$|w|_a$ divisble by $3$ means $w$ has exactly $3k$ $a$'s in it? – Aryabhata Feb 25 '12 at 18:32
@Aryabhata precisely – Daniil Feb 25 '12 at 18:34

## 1 Answer

How sure are you that the language isn't regular? If I understand your description of it correctly, it is generated by the regular expression $$B \mid a B b \mid aa B bb \qquad\text{where }B = b^* (ab^* ab^* ab^*)^*$$ In the cases for $k=3n+m$ with $n>1$ and $0<m\le 3$ you can just reinterpret $a^kwb^k$ as $a^m(a^{3n}wb^{3n})b^m$.

-
You are absolutely right, thank you. Can you please elaborate on how did you manage to find the answer? Did your intuition tell you that the language is regular? – Daniil Feb 26 '12 at 8:35
@Daniil: I tried to prove that a deterministic automaton would need infinitely many states to recognize the the language, but kept running into problems with the details. Eventually, while trying to patch them up, I discovered a counterexample. Then I spent a few minutes figuring out how to express it as a regular expression because otherwise I'd have to draw my counterexample automaton in the answer. :-) – Henning Makholm Feb 26 '12 at 13:31