Prove the following language is not regular using the pummping lemma
$L = \{a^{n!} \mid n\geq0, n\in\ \mathbb{N} \}$.
What I have done so far is:
Assume $L$ is regular. So, there is a $DFA$ for $L$ with $m$ states.
Let $w\in L, w=a^{m!}=a^ma^{m!-m}$, it is easy to notice that $|w|\geq m$.
$$x=a^t \space\space\space, \space\space\space y=a^k \space\space\space, \space\space\space z=a^ja^{m!-m}$$
$$t+k+j=m \space\space\space and \space\space\space1\leq k\leq m$$
According to the pumping lemma our $DFA$ accepts all words that looks like:
$$w'=a^ta^{k\cdot i}a^ja^{m!-m}$$
Lets take a look when $i=2$
$$w'=a^ta^ka^ka^ja^{m!-m}=a^{m+k}a^{m!-m}=a^{m!+k}$$
We remember that $1\leq k\leq m$, therefore $m!+1\leq m!+k\leq m!+m$.
I am stuck at this point. Any help is welcome!
Best Answer
All you have to do is observe that if $m > 1$ then (continuing your proof) $$ m! < m! + m < 2m! < (m+1)! $$ On the other hand, if $m = 1$ then $k=1$ and for $i=3$ you get $$ 2! < |w'| = m! + 2k = 3 < 3! $$ Either way, $w' \notin L$ because every word in $L$ has factorial length, but this contradicts the pumping lemma.
Your notation is a bit cluttered. Below I wrote a shorter (but equivalent) proof using the statement and notation from Wikipedia.
Now, let $p$ as above for your language and fix an $n$ such that $n! \geq \max(2,p)$. Then consider the factorization of the word $a^{n!} = xyz$ like in the statement of the lemma. By 3. we know that $xy^2z \in L$, but this is absurd because $$ n! < |xy^2z| = n! + |y| \leq n! + p \leq 2n! < (n+1)n! = (n+1)! $$