Show that {xy : x,y ∈ {a,b}*, |x| = |y|, x ≠ y} is a not a regular language

Actually, I know that there are many examples showing how this is a contex-free language, but I can't find any that show it isn't regular. I would appreciate if I could have a solution step by step for this case Show that {xy : x,y ∈ {a,b}*, |x| = |y|, x ≠ y} is not a regular language

• Use the pumping lemma. Its basically almost single handedly the best tool to prove non-regularity Oct 20 '21 at 13:47
• As pointed out, proving that this language is not regular is an exercise in using the pumping lemma. This reference question should be helpful. Oct 20 '21 at 15:00

You need to use the concept of pumping lemma.

1. Define a pumping length, $$p$$

2. Choose a word, $$w\in L$$ such that $$|w|\geq p$$

3. Split $$w$$ into three constituent parts, $$x,y,z$$ such that $$y\neq\varepsilon$$ (but $$x$$ and $$z$$ are allowed to $$=\varepsilon$$), $$|xy|\leq p$$, and $$xy^kz$$ is in your language $$L$$ for any $$k \geq0$$.

4. Let's leave $$p$$ undefined as $$p$$ for this, and take the word $$a^p b^p$$ which satisfies the rules of the language

5. $$|w|=2p\geq p$$ therefore the condition in step 2 is met

6. Now we split up $$w$$. With the rules defined, $$y$$, the important bit, must be in the first $$p$$ characters of $$w$$, meaning that it must be made up entirely of $$a$$'s, so let's take $$x=a$$, $$y = a^{p-1}$$, $$z=b^p$$ (but it doesn't matter whether $$y$$ is $$a^1$$, or $$a^p$$, and $$x=\varepsilon$$ or $$x=a^{p-1}$$, the outcome is the same).

7. Now for the important part - if we pump the string such that $$xy^0z$$, we get $$a(a^{p-1})^0b^p=ab^p$$ which you'll observe is $$\notin L$$.

8. In fact, whatever we use as $$k$$ to pump $$y$$, we'll always end up with a scenario where $$|x|\neq|y|$$, and this would be the same whatever string you used from your language.