1
$\begingroup$

I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

Question

Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma. I know the correct way of prove with factorial or using closure. However today someone explain a way to me and I couldn't find what is wrong with it. I think it is wrong but if it is true, is it possible to explain why?

Proof (Maybe correct):

we suppose that that $L$ is regular and there is a machine with $u$ state that accept it. If it is a NFA, we can convert any NFA to DFA with for example $k$ state.
We have a group of strings like $a^kb^{k + t}$ for every $1 \le t \le k$ which accepted with machine.
There is only one way for read $a^k$ because our machine is DFA so we can write $a^k = a^sa^ta^p$ that $|a^sa^t| \le k$ and $|a^t| \ge 1$ and $a^t$ is cycle, so with pumping lemma we can say that $a^{k + t}b^{k + t}$ (with one more time of cycle) belongs to $L$ and it is contradiction. (one of our strings in our first group will fail) so our language is not regular.


My Problem

Because we we get a group of strings (instead just one strings which is normal in proves) and use same $t$ when break $a^k$ to $a^sa^ta^p$, is it true anymore? If no or yes, please explain.

My explanation

I think we can construct a NFA that accept each of $a^kb^{k + t}$ (for each $t$) with different size of cycle (cycle that is used in pumping lemma) however when convert it to a DFA, I can't understand how to prove it.

$\endgroup$
1
$\begingroup$

This is a trick question. Your proof doesn't quite work, but can be turned into a proof, as follows.

Let $p$ be the constant in the pumping lemma, and consider the word $a^pb^{p+p!} \in L$. According to the pumping lemma, it can be decomposes as $xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Since $|xy| \leq p$, we must have $y = a^q$ for some $q \leq p$; since $y \neq \epsilon$, we must have $q \geq 1$. Let $i = p!/q + 1$. Then you can check that $xy^iz = a^{p+p!} b^{p+p!} \notin L$, contradicting the pumping lemma.

Here are two more proofs. The first uses closure properties. If $L$ were regular then so would the following language be: $a^*b^* \setminus L = \{ a^nb^m : n = m \}$. However, this language is known to be non-regular.

Another proof uses Myhill–Nerode theory. Let us say that two words $x,y$ are incomparable if there exists a word $z$ such that $xz \in L$ but $yz \notin L$, or vice versa. In any DFA for $L$, we must have $\delta(q_0,x) \neq \delta(q_0,y)$ (why?). Therefore, if we can find an infinite collection of pairwise incomparable words, then the language is not regular (why?). In the case of $L$, such a collection consists of the words $a^i$ for all $i \geq 0$. Indeed, if $i \neq j$ then $a^ib^j \in L$ whereas $a^jb^j \notin L$, showing that $a^i,a^j$ are incomparable.

$\endgroup$
  • $\begingroup$ Thanks for answer. as I mentioned, I know the correct way of prove (the method 1 and method 2 which you said) and method 3 is very beautiful. however I want to know what is wrong about that answer in question or if it is true, prove it. Is it possible to help me? $\endgroup$ – Amin Oct 29 '18 at 3:54
  • $\begingroup$ Well, your proof doesn't work. It doesn't "compile", i.e., doesn't constitute a formal argument. One correct way to implement the same idea is method 1. $\endgroup$ – Yuval Filmus Oct 29 '18 at 3:57
  • $\begingroup$ I know that is not correct but I can give a strong statement which state that is not correct for my friend. can you explain exactly which part of proof is not correct and why? $\endgroup$ – Amin Oct 29 '18 at 4:30
  • $\begingroup$ The part starting “there is only one way”. $\endgroup$ – Yuval Filmus Oct 29 '18 at 6:21
  • $\begingroup$ why? because it is DFA and it is only one way? can you explain more. $\endgroup$ – Amin Oct 29 '18 at 6:50

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.