Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular

Question

Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b \}$ is not regular.

I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. Could someone please help me?

I tried to use the pumping lemma with the word $w=a^{2p}b^p$. It is easy to see that for $p=1$ it cannot be "pumped". However, for the case $p=2$ and, particularly, splitting the string $w=aaaabb$ into $x=\lambda$, $y=aa$ and $c=aabb$, it is true that $\forall i \quad xy^iz\in L$ . Examples for the case $p=2$ are: $i=0 \mid w=aabb$ which can be split into $x=aab$ and $y=b$, $ i =1 \mid w=aaaabb$ into $x=aaaa$ and $y = bb$, $ i =2 \mid w=aaaaaabb$ into $x=aaaa$ and $y = aabb$, etc. So we can't reach to a contradiction.

Answer 1

Here are several routes to proving this:

• Intersect with $a^*b^*$ and apply an appropriate inverse homomorphism to reduce to the language $\{a^nb^n : n \ge 0 \}$, which you know isn't regular.
• Use Myhill–Nerode theory: the words $\{a^n : n \geq 0\}$ are pairwise inequivalent.
• Use the pumping lemma on the word $a^{2p} b^p$, where $p$ is the pumping constant.