An NFA with $\Sigma = \{1\}$ with $x^2$ accepting runs on strings $1^x$ for all $x \geq 0$ - how to construct?

Question

One of my homework assignments requires us to construct an NFA over the alphabet $\{1\}$ which has exactly $x^2 + 3$ accepting runs over the input string 1^x for all $x \in \mathbb{N}$. Now, the +3 part is simple - I've got LaTeX code for a state diagram for this using tikz automata:

(Now with a pretty diagram!)

However, the $x^2$ part is proving really hard for me to figure out. I'm not sure how to do this with a finite number of states, and because this is an NFA, this is especially tricky. Any and all suggestions of how to think about this and what approach to take would be very helpful.

Answer 1

There's no such NFA.

Assume there was an NFA over the alphabet ${1}$ which accepts all strings whose length is $n^2 + 3$ for some $n \in \mathbb{N}$. I.e., the NFS is supposed to accept strings of lengths $3,4,7,12,19,28,39,\ldots$.

If there was such an NFS, the language $$ \Omega = \left\{\underline{1}^{n^2+3} \,:\, n \in \mathbb{N}\right\} $$ would be regular. According to the pumping lemma for regular languages, we'd then have an $N$ such that if $x \in \Omega$ and $|x| \geq N$, then there are $x_l,x_2,x_3$ with $|x_2| > 0$, $x_1x_2x_3=x$ and $x_1\underbrace{x_2\ldots x_2}_{k\text{ times}}x_3 = x_1x_2^kx_3 \in \Omega$ for all $k \geq 1$.

For our language, that implies there there's an $N$ such that if for some $x > N$ there's an $n \in \mathbb{N}$ with $x = n^2 + 3$, then the same thing works for $x + mx_2$ ($x_2 \neq 0$) for all $m \geq 1$. Set $z = x-3$, then the statement is $$ z \geq N, z \text{ is a square} \implies \exists{x_2\in\mathbb{N}^+}:\, \forall m \geq 1:\, z + mx_2 \text{ is a square}\text{.} $$ That's obviously impossible, since the distance between two consecutive squares gets larger and larger, and once it get's larger than $x_2$, the right-hand side cannot hold.

Answer 2

Here is a solution of what I think was the original question (See the comment by Arthur Fischer). This solution gives a 7-state NFA (without $\varepsilon$-transitions), such that for each $k \geqslant 0$ there are exactly $k^2+3$ different accepting runs on input $^k$. Note that for $k = 0$, there are exactly three accepting runs, and hence there must be three initial states which are also final. Here is the solution.

Note that $2$ is the unique nonfinal state (this is not a typo). On input $^k$, there are $1 + \frac{k(k-1)}{2}$ accepting runs starting in state $1$, $1 + \frac{k(k+1)}{2}$ accepting runs starting in state $4$ and $1$ accepting run starting in state $7$. The total is $k^2 + 3$.