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

  • 2
    $\begingroup$ Use the pumping lemma. Its basically almost single handedly the best tool to prove non-regularity $\endgroup$
    – nir shahar
    Oct 20 '21 at 13:47
  • 2
    $\begingroup$ As pointed out, proving that this language is not regular is an exercise in using the pumping lemma. This reference question should be helpful. $\endgroup$
    – mursalin
    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.


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.