In the alphabet $\Sigma=\{0,1\}$, I need to prove that this language is not regular. I've tried using the pumping lemma, choosing the string $a(ab)^p(ba)^p$ for a given $p$, any possible choose of a decomposition $xyz$ of the string such that $|xy|<p$ is such that $xy$ is of the form $a(ab)^l$ or $a(ab)^la$. But there are so many possible forms for $y$ that I'm stuck here.

I know there are some similar questions like this, but they use some strange logic that if you can't apply some trick related to "extending" x then the lenguage is not regular, this trick works with languages like $\{wxw^r\mid w,x \in \{0,1\}^+\}$ but only because it's the same language with strings that start and end in the same character.


Your Answer

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

Browse other questions tagged or ask your own question.