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

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.

• I suggest you show your attempts with those methods and where you got stuck or why they failed. – D.W. Apr 7 '19 at 23:52
• Here is a hint. Try pumping $a^{2p}b^p$. – John L. Apr 8 '19 at 1:01

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