# Proving language is not regular using pumping lemma

Show that the language

$L =$$\left \{ a^{n!} : n\geq 1 \right \}$ is not regular using pumping lemma

My solution is :

Suppose L is regular

There exist some pumping length for L, let it be "m"

We don't know the value of m but whatever it is we can always choose n = m.

Then from the pumping lemma there exists $x, y, z \in Σ^{∗}$ such that w = xyz , |xy| ≤ m and |y| ≥ 1.

$w_{i} = xy^{i}z$

y must contain entirely of a's

suppose $|y|=k$

the string obtained by i = 1 is,

w = $a^{m!+k}$

Now after this i'm stuck because how can i prove $m!+k$ cannot be accepted by the language

also if i chose i = 0 then also i'm stuck

Pick $i$ such that $m! + ik \neq h!$ for some $h$, and you are done. In particular, if $i=1$, then $m! + k \leq m! + m \neq (m+1)!$.
• but how can we pick k? are we allowed to pick k anywhere between $1 \leq k \leq m$ that helps in contradiction? – Mk Utkarsh Mar 20 '18 at 9:58
• I misread your proof a little. You want to select $i$ appropriately. See my edit. – ml0105 Mar 20 '18 at 13:00
• Suppose L is regular There exist some pumping length for L, let it be "m" We don't know the value of m but whatever it is we can always choose n = m. Then from the pumping lemma there exists $x, y, z \in Σ^{∗}$ such that w = xyz , |xy| ≤ m and |y| ≥ 1. $w_{i} = xy^{i}z$ y must contain entirely of a's suppose $|y|=k$ the string obtained by i = 1 is, w = $a^{m!+k}$ we know that k $\geq$1 so if 1 $\leq$ k $\leq$ m $m!$ $<$ $(m! + k)$ $<$ $(m+1)!$ hence we can say that $a^{m!+k}$ $\notin L$ Hence our assumption of L being regular was wrong and L is not regular. – Mk Utkarsh Mar 20 '18 at 19:45
• Pick $i=2$. Note that for $i=1$, $y^{i} = y$. – ml0105 Mar 20 '18 at 19:48