Some of you have attempted to show that \( L_{\neq} \) is not a regular language by directly applying the pumping lemma, without using any closure properties of the regular languages as done in class. Here is a solution that has been found in past years by a former student, Simone Dalla Valle.
The proof reported below also answers to a question by an other student who approached me after the lecture, who asked if language \( L_{\neq} \) is an example of a language which is not regular but satisfies the pumping lemma: the answer is no, \( L_{\neq} \) does not satisfy the pumping lemma, as shown below.
Let \( L_{\neq} = \{ a^{n} b^{m} | n \neq m \), \( n, m \geq 1 \} \) and assume \( n \) is the pumping lemma constant. Choose the string \( w = a^{n} b^{n + n!} \in L_ \neq \).
In any factorisation \( w = xyz \) satisfying the pumping lemma, the string \( y \) can only contain occurrences of symbol \( a \) and we must have \(|y| = m \geq 1\).
If we iterate \( k \) times the string \( y \), we obtain \( w_{k} = xy^{k}z \) where \( \#_{a}(w_{k}) = (n - m) + k m = n + ( k - 1) m \).
We then let \( k = \frac{n!}{m} + 1 \). Note that this is a valid choice for \( k \) since we have \(1 \leq m \leq n \) and \( \frac{n!}{m} \in \mathbb{N} \).
We then have \( \#_{a}(w_{k}) = n + \frac{n!}{m} m = n + n! \) and \( w_k = a^{n + n!} b^{n + n!} \notin L_ \neq \) since \(\#_{a}(w_{k}) = \#_{b}(w_{k}) \).
We have found a violation of the pumping lemma and we therefore conclude that \( L_{\neq} \) is not a regular language.