1
$\begingroup$

I'm trying to prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular and, although it's trivial to prove it via pumping lemma, I'm having troubles trying to find a way to prove it via closure properties (for example a union of $L$ and another regular language which may give a non-regular language).

It simply doesn't occur to me any language to use alongside $L$ (I guess I lack some imagination...)

$\endgroup$
3
$\begingroup$

Consider the intersection of your language $L$ with the regular language $L' = \{b^r a^m \mid r,m \ge 0 \}$. Then $L \cap L'$ contains all the words of the form $a^k b^r a^m$ where $k=0$ and $m=k+r=r$. That is, $L \cap L' = \{ b^r a^r \mid r \ge 0 \}$, which is a well-known non-regular language.

$\endgroup$
1
  • 1
    $\begingroup$ wow, that was quite simple and tricky. Thank you (again!) $\endgroup$
    – Lightsong
    Feb 3 at 14:48

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.