2
$\begingroup$

Proving the language $L=\{ a^i b a^j |\ i<j,\text{ or }i>j;\ i,j>0 \} $ is not regular, I am trying to use the pumping lemma for regular languages:

pumping length $:= m$

case 1: $i<j; j=m$

$w_1 = a^i b a^m = xyz$
$|xy| < m$
$|y| > 0$

$\Rightarrow$
$y$ can be:

  • $a$s only
  • $a$s + $b$
  • just $b$

However, this leads to $xy^hz\ \not \in L\ \forall h,\ h>0$.

case 2: $i>j; i=m$

$w_2 = a^m b a^j = xyz$
$|xy| < m$
$|y| > 0$

$\Rightarrow$
$y$ can be:

  • $a$s only

Pumping with this $y$:
$xy^hz\ \in L\ \forall h$ holds true.

As this answer does not seem to even consider the second case, is the first case sufficient to proof the language is not regular?
However, taking a look at this answer I think I'd have to considere the second case as well, in order to cover all possible $xyz$ combinations.

$\endgroup$
  • $\begingroup$ I don't understand your attempted proof – what is your starting word? In any case, we don't check proofs here. It's not clear what you mean by first case / second case, but to use the pumping lemma it suffices to use a single starting word, and then you need to check all of its possible partitions, and to show that each one can be pumped out of the language. $\endgroup$ – Yuval Filmus Feb 23 '17 at 20:27
  • $\begingroup$ But how can you describe it with the conditions: $i<j\text{, or }i>j$ in one word? $\endgroup$ – cocoseis Feb 23 '17 at 20:37
  • $\begingroup$ To prove that a language is not regular using the pumping lemma, you choose a word in the language (given the pumping constant) and show that it doesn't satisfy the pumping property. You can choose any word you want, as long as it's not shorter than the pumping length. $\endgroup$ – Yuval Filmus Feb 23 '17 at 20:40
  • $\begingroup$ In other words, case 1 is sufficient? $\endgroup$ – cocoseis Feb 23 '17 at 20:42
  • 1
    $\begingroup$ Yes, a single word suffices. $\endgroup$ – Yuval Filmus Feb 23 '17 at 20:42
1
$\begingroup$

Here is the contrapositive form of the pumping lemma, which is what we use to prove that a language is not regular:

Let $L$ be a language. Suppose that for all $p \geq 1$ there exists a word $w \in L$ of length at least $p$ such that for every decomposition $w=xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Then $L$ is not regular.

Using the pumping lemma directly for the language $L$ in the question is a bit tricky. Given $p \geq 1$, let $w = a^p b a^{p+p!} \in L$; note that $|w| \geq p$. We have to show that for every decomposition $w = xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Consider any such decomposition. It is easy to check that $y = a^\ell$ for some $1 \leq \ell \leq p$, and that $xy^ij = a^{p+(i-1)\ell}ba^{p+p!}$. For $i = p!/\ell+1$ (which is an integer!), $xy^ij = a^{p+p!}ba^{p+p!} \notin L$. Thus the condition in the pumping lemma is satisfied, and we conclude that $L$ is not regular.

$\endgroup$
1
$\begingroup$

Let $$L_1 = \{a^iba^j | i\lt j\text{ and } i,j\gt 0\}$$ $$L_2 = \{a^iba^j | i\gt j\text{ and } i,j\gt 0\}$$

Here, $$L = L_1\cup L_2$$

From Case 1, you have shown that $L_1$ is not regular.

You are trying to conclude that if $L_1$ is not regular, $L$ is not regular. It is not sufficient that $L_1$ is not regular to show that $L$ is not regular. A simple counter example will be $L_1 = \{a^nb^n|n\gt 0\}$ and $L_2=\{a^m b^n |m\ne n\}$. Neither $L_1$ nor $L_2$ are regular, yet their union is regular.


In the first answer you have linked, it is not true that only one case has been considered. You need to find any one string $s$ whose length is at least than every possible pumping length $p$ such that no matter how you partition it into $s=xyz$, the resulting string goes out of the language.

The key difference between your case 1 and the answer you linked is that you have taken a string in $L_1\subset L$, pumped it and shown that it goes out of $L_1$ only. However, what you need to show is that it cannot lie in $L$ at all, no matter how you split it and pump it, which is what the linked answer shows.

$\endgroup$

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.