1
$\begingroup$

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.

  • 0
    @Aryabhata precisely2012-02-25

1 Answers 1

3

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 you can just reinterpret $a^kwb^k$ as $a^m(a^{3n}wb^{3n})b^m$.

  • 1
    @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. :-)2012-02-26