Explaining Ultimate Periodicity.

Question

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$

Welcome to MSE. In MathJax (and in LaTeX) { and } can be used to enclose the argument of a command, so the code for $a^{n^2}$ is a^{n^2}. — A.P., Apr 20 '15 at 15:25
I don't really understand what the answer from your booklet is supposed to be. More importantly, though, could you tell us which definition of regular language are you using? — A.P., Apr 20 '15 at 15:29
The regular language shouldn't make a difference. I updated the question's answer part with the full proofing from the book. — Marc, Apr 20 '15 at 15:50

score 1 · Accepted Answer · answered Apr 20 '15 at 18:53

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

Explaining Ultimate Periodicity.

1 Answers1