1
$\begingroup$

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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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