1
$\begingroup$

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.

$\endgroup$

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.