I'm revising for an exam and I've stumbled by Ultimate Periodicity.
The exercise is:
Prove that $A = \left\{ a^{n^2} \mid n \in \Bbb{N} \right\}$ isn't regular.
Can someone explain how we get to an answer with this, an explanation of the variables?
The answer booklet gave this:
Say that A is regular. Then $\{n^2 | n ∈ \mathbb{N}\}$ is eventually periodic. That means to say, $∃ N, p ∈ \mathbb{N}$ Such that $ p \geq 1$ and $\forall \,m \geq N \, m^2 ∈ A ⇐⇒ m^2 + p ∈ A $
$\max\{N,p\}+1, m^2 < m^2+p < m^2+m ≤ m^2+2m+1 = (m+1)^2$
Consider a DFA $M$ that recognizes an infinite regular language $L$ over the alphabet $\{a\}$. Then $M$ must have the following form:
$$\begin{array}{ccc} q_0&\longrightarrow&q_1&\longrightarrow&\ldots&\longrightarrow&q_m&\longrightarrow&q_{m+1}&\longrightarrow&\ldots&\longrightarrow&q_n\\ &&&&&&\uparrow&\longleftarrow&\longleftarrow&\longleftarrow&\ldots&\longleftarrow&\downarrow \end{array}$$
That is, it must consist of an initial segment, possibly empty (if $m=0$), followed by a loop. If $A$ is the set of acceptor states, let
$$I=\{k:0\le k<m\text{ and }q_k\in A\}$$
and
$$C=\{k:m\le k\le n\text{ and }q_k\in A\}\;.$$
Let $d=n-m+1$. Then
$$\{n:a^n\in L\}=I\cup\{kd+c:c\in C\text{ and }k\in\Bbb N\}\;.$$
(Note that for me $0\in\Bbb N$.) Thus, there are an $m\in\Bbb N$ and a $d\in\Bbb Z^+$ such that if $a^n\in L$ and $n\ge m$, then $a^{n+d}\in L$. That is, the set of lengths of words of $L$ is eventually periodic with period $d$. (The eventually refers to the possible existence of an initial segment of lengths of words that don’t reach the cyclic part of $M$.)