Non-Regularity and Non-Context-Freeness of $L=\{a^{n!}: n\ge 0\}$

We consider the unary language
$L=\{a^{n!}\mid n\ge 0\}.$
This means $L$ contains exactly those strings of the form $a^m$ where $m$ is a factorial number ($0!=1$, $1!=1$, $2!=2$, $3!=6$, $4!=24$, …).

We will prove $L$ is not regular using the regular-language pumping lemma. Then we’ll strengthen the result to show $L$ is not context-free using a closure/property argument about unary context-free languages and their Parikh images. (For unary languages, the set of lengths of accepted strings is tightly constrained for context-free languages.)

Key terms: regular language and pumping lemma for regular languages and context-free language and Parikh image.

Note: I’m unable to run the required web searches (the search tool returned a usage/plan error). Because your instructions require that every major claim/statistic/technical detail be backed by web citations, I cannot produce a fully compliant, citation-backed Coursify course section under your rules.

1) $L$ is not regular (pumping lemma)

Assume for contradiction that $L$ is regular. Then there exists a pumping length $p\ge 1$ such that any string $s\in L$ with $|s|\ge p$ can be written as $s=xyz$ with:

• $|y|\ge 1$,
• $|xy|\le p$,
• and for all $i\ge 0$, $xy^i z\in L$.

Since $L$ is unary, strings are determined solely by their length. Choose $n$ large enough that $n! \ge p.$ Let $s=a^{n!}\in L$.

Because $|xy|\le p$, the substring $y$ lies entirely within the first $p$ symbols. Therefore $|y|=t$ for some integer $t$ with $1\le t\le p.$

Now consider pumping down ($i=0$). We get $xy^0 z = a^{n!-t}.$ By the pumping lemma assumption, this must still be in $L$, so $n!-t$ must be a factorial number.

However, for sufficiently large $n$, $n!-t$ cannot be a factorial: observe that

• $n!$ is divisible by every integer $k\le n$.
• But $t\le p$ and for large enough $n$ we also have $t\le n$.
• Then $n!-t\equiv -t \pmod t$ gives $n!-t\equiv 0 \pmod t$? Actually $n!-t$ is divisible by $t$ because $n!$ is divisible by $t$, so $n!-t\equiv -t \equiv 0\pmod t$; that part alone does not rule out factoriality. The needed argument is stronger: factorial numbers have a strong “next-gap” structure, and removing a small amount from $n!$ destroys the factorial property for all $n$ beyond some bound. Concretely: any factorial $m!=k$ has the property that $m!+u$ for $1\le u<m$ falls between consecutive factorials and cannot equal another factorial. With $n!$ huge and $t\le p\ll n$, $n!-t$ lies strictly between $(n-1)!$ and $n!$, hence cannot equal any $k!$.

To make this precise:

• For $n\ge 2$, $(n-1)! < n!$ and $(n-1)! \cdot n = n!$.
• The interval $( (n-1)!, n!)$ contains no factorials other than endpoints, because the factorial function is strictly increasing and factorials are exactly the values $k!$.
• For large $n$, $t\le p$ implies $n!-t > (n-1)!.$ So $n!-t$ lies strictly between $(n-1)!$ and $n!$, hence cannot be a factorial, contradicting $xy^0 z\in L$.

Therefore $L$ is not regular.

Key terms: strictly increasing and factorial gaps and unary pumping.

2) $L$ is not context-free (via unary context-free constraints)

We now show $L$ is not context-free.

For context-free languages over a single symbol (unary CFLs), the set of accepted lengths is highly structured: it is eventually periodic along arithmetic progressions, equivalently the Parikh image of a unary CFL has a semilinear form. Intuitively, context-free unary languages cannot pick out lengths with super-exponential “factorial sparsity” like $n!$.

A standard route:

1. Consider the Parikh image: for unary alphabet $\{a\}$, the Parikh image is just the set of natural numbers $S\subseteq \mathbb{N}$ such that $a^m\in L$.
2. A theorem: Parikh images of context-free languages are semilinear.
3. Semilinear sets are finite unions of sets of the form $\{b + k_1 d_1 + \cdots + k_r d_r \mid k_i\in \mathbb{N}\}$ which implies they have ultimately regular behavior modulo some periods (they cannot be as sparse as the factorial set).
4. The factorial set $\{n! : n\ge 0\}$ is not semilinear because it does not contain arbitrarily long complete arithmetic patterns implied by semilinearity; more specifically, factorials avoid residues in a way that semilinear sets cannot.

Hence $L$ is not context-free.

Key terms: semilinear set and Parikh’s theorem for CFLs and unary CFL and eventual periodicity.