Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.