# Proving irregularity of $a^{k!}$ using Nerode's theorem

Use Nerode's theorem to prove that the following language $$L$$ is not regular:

$$L=\{a^{k!} \mid 1\leq k\}$$

Here is my attempt:

Let $$A$$ be an infinte set of words s.t- $$A=\{a^n \mid n\in \mathbb{N}\}$$

Then we shall consider 2 words from the set $$a^{i!}$$ and $$a^j$$ s.t-
$$i!\leq n, i!\ne j$$

$$a^{i+1} \longrightarrow a^{i!}\cdot a^{i+1}=a^{(i+1)!}\in L$$ $$a^j\cdot a^{i+1}=a^{j+i+1}\notin L$$

I understand my attempt is not correct since when multiplying $$a^{i!}\cdot a^{i+1}$$ the exponent doesn't multiply . I cant seem to overcome this obstacle and would appreciate help.

• I don't understand your attempt, since it doesn't contain any words. Dec 13, 2021 at 18:23
• Also, what is your question? Is it whether your attempt is correct or not? We typically don't grade homework solutions, which is your TA's job. Dec 13, 2021 at 18:24
• @YuvalFilmus I edited my attempt and clarified my question
– ATB
Dec 13, 2021 at 18:36

You can prove the following using Myhill-Nerode: If $$x_n$$ is a non-decreasing sequence, and the differences $$x_{n+1} - x_n$$ are not bounded, then the language $$\{a^{x_n}\}$$ is not regular.
That covers lots of problems that you will find in a course, like your n!, or $$a^p$$ where p is prime, or $$a^{n^2}$$, or any infinite subsequence of such sequences.
Someone else asked about the language $$\{0^{2^n}\}$$. Same solution.