prove this $L$ is not regular?

160 Views Asked by At

Consider the language $L=\{a^{n!}\mid n\in\mathbb{N}\}$.
I want to prove that $L$ is not regular using the Pumping Lemma.

So far i assumed by contradiction that $L\in REG$, so it has a pumping constant $p\in\mathbb{N}$ that stands for all of the conditions of the pumping lemma.
Now, i'm looking at $w=a^{p!}$.Clearly $|w|>p$, So there are $x,y,z\in\sum^{*}$ such that $w=xyz$, and from the lemma , for every $i\in\mathbb{N\cup}\{0\},x\cdot y^{i}\cdot z\in L$. If i choose $i=p$, we get $a^{p+p!}$, but from here i stuck.
How to prove that $p+p!$ is not factorial of another number? And if i totally not in the right direction, how to prove it but still with the pumping lemma?

1

There are 1 best solutions below

0
On BEST ANSWER

Notice that $n!$ is even number for all $n>1$

Choose the word $z=a^{p!}$ and $\mid z\mid\ge p$

Let's assume that $p>1$

$$z=uvw$$

$$1.\quad |uv|\le p$$

$$2.\quad |v|\ge 1$$

$$3.\quad uv^iw\in \mathcal L$$

So $z=\underbrace{aaa\dots a}_{ p!\text{ times}}$

and $ p!$ is even so choose $i=2$ you will get a word with odd length $ p!+1$