1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Right off the bat, $q$ isn't an integer (since there's no maximum integer). $\endgroup$ Apr 18, 2018 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, 2018 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$ Apr 18, 2018 at 8:54

1 Answer 1

2
$\begingroup$

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^*$.

$\endgroup$
5
  • 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$ Apr 18, 2018 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$
    – bkahso
    Apr 18, 2018 at 14:48
  • $\begingroup$ @bkehs since max(I,j) doesn’t exist $\endgroup$
    – Wenzel
    Apr 18, 2018 at 14:54
  • $\begingroup$ Does $ | i - j| $ exist and could that be used instead? $\endgroup$
    – bkahso
    Apr 18, 2018 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$
    – Wenzel
    Apr 18, 2018 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.