Proving language is not regular using pumping lemma

Question

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

ml0105 · Accepted Answer · 2018-03-20 12:56:59Z

1

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)!$.

Your proof otherwise looks good!

answered Mar 20, 2018 at 6:05

ml0105

14.8k2 gold badges25 silver badges49 bronze badges

$\begingroup$ but how can we pick k? are we allowed to pick k anywhere between $1 \leq k \leq m$ that helps in contradiction? $\endgroup$
– Mk Utkarsh
Commented Mar 20, 2018 at 9:58
$\begingroup$ i read Introduction of formal languages and Automata by peter linz and we cannot choose the decomposition of string. correct me if i'm wrong $\endgroup$
– Mk Utkarsh
Commented Mar 20, 2018 at 10:02
$\begingroup$ I misread your proof a little. You want to select $i$ appropriately. See my edit. $\endgroup$
– ml0105
Commented Mar 20, 2018 at 13:00
$\begingroup$ 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. $\endgroup$
– Mk Utkarsh
Commented Mar 20, 2018 at 19:45
1

$\begingroup$ Pick $i=2$. Note that for $i=1$, $y^{i} = y$. $\endgroup$
– ml0105
Commented Mar 20, 2018 at 19:48

| Show 1 more comment

1 Answer 1