Prove that $L_2 = \{ w \in \{a,b\}^* \mid w = a^ib^j, i \neq j \}$ is not regular.

I was wondering if my intuition holds for proving this language as not regular:

Let $q = \max(i, j) - \min(i, j)$.

Case 1: $i > j$

Let $$L_3 = b^q \Rightarrow L_2 \cdot L_3 = \left \{ a^ib^{j+q} \right \}=\left \{ a^ib^i \mid i \ge 0 \right \}.$$

And then do the same for when $j > i$.

Is this allowed?

  • $\begingroup$ Right off the bat, $q$ isn't an integer (since there's no maximum integer). $\endgroup$ – Rick Decker Apr 18 '18 at 0:09
  • $\begingroup$ Welcome to Computer Science! Your question is a rather basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Apr 18 '18 at 5:06
  • $\begingroup$ Your intuition is not so clear. At any rate, there is a big difference between "feelings" and proofs, even proof ideas. $\endgroup$ – Yuval Filmus Apr 18 '18 at 8:54

No that's not allowed, since $i$ and $j$ are not fixed.

Here is a solution using pumping lemma:

The better approach is to apply pumping lemma. Let $x = a^{n!}b^{(n+1)!}$, where $n$ is the pumping constant. Note that $u = a^i$ and $v=a^j$ for some $i\geq 0$ and $j>0$ plus $i+j\leq n$. Then we let $k = 1+\frac{n\cdot n!}{j}$. After that, $uv^kw = a^mb^{(n+1)!}$ where $m = n!+(k-1)j = n!+n\cdot n! = (n+1)!$. Contradiction.

Here is another solution using closure result (which is less tricky):

Suppose $L_2$ is regular. Then $(\Sigma^* - L)\cap a^*b^* = \{w\in\{a, b\}^*|w=a^ib^j, i=j\}$ is regular by closure result. Then it's easy to gain a contradiction by applying pumping lemma to $(\Sigma^* - L)\cap a^*b^*$.

  • 2
    $\begingroup$ A simpler approach (which doesn't require knowing any tricks) is to use Myhill–Nerode theory. For $i \neq j$, the words $a^i,a^j$ are inequivalent since $a^ib^i \notin L_2$ while $a^jb^i \in L_2$. Hence there are infinitely many equivalence classes in the Myhill–Nerode relation, and so the language is not regular. $\endgroup$ – Yuval Filmus Apr 18 '18 at 8:55
  • $\begingroup$ Thank you for your reply! However, just because i and j are not fixed, why does that translate into not being able to calculate the difference between them? They could vary, but in any case they must be unequal and therefore must have a difference between them. $\endgroup$ – bkehs Apr 18 '18 at 14:48
  • $\begingroup$ @bkehs since max(I,j) doesn’t exist $\endgroup$ – Wen Apr 18 '18 at 14:54
  • $\begingroup$ Does $ | i - j| $ exist and could that be used instead? $\endgroup$ – bkehs Apr 18 '18 at 14:57
  • 1
    $\begingroup$ @bkehs Since $i$ and $j$ can be any number if only they are not equal, $|i-j|$ is actually equivalent to $N^+$, which is kinda useless. $\endgroup$ – Wen Apr 18 '18 at 15:14

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.