# Characterization of lengths of words accepted by DFAs

Let $$M$$ be an arbitrary DFA. For each $$n \in \mathbb{N}$$, let $$f_M(n)$$ be the number of words of length $$n$$ accepted by $$M$$. Then, consider the set of all such $$f_M$$ for all DFAs $$M$$.

Is there a nice characterization of such a set of functions? How does the set change if we restrict the number of states in the DFA, or the number of letters in the alphabet of $$M$$, or if we make $$M$$ an NFA? Any relevant information would be appreciated.

## Examples:

DFA Image $$f_M(n)$$ $$\binom n2 = \begin{cases}\frac{n^2-n}2 & n \geq 2 \\ 0 & n < 2\end{cases}$$
• Since you can do $\Sigma^*$ with a DFA having one state, I do not think restricting the number of states is relevant.
– holf
Jun 1, 2022 at 20:10
• @holf But such an automaton could only have $f_M(n) = c^n$ for $c$ transitions to itself, whereas you could get different functions from more complicated DFAs.
– Jake
Jun 1, 2022 at 20:54
• OK I see. Maybe it is already known but I have the impression that: either your language is finite, or $f_M$ grows linearly, or $f_M$ grows exponentially. The condition being either there is no loop, or for every state $q$, there is at most one simple path from $q$ to $q$, or you have some state $q$ having two simple path from $q$ to $q$. Let's say the first one is labeled with $w$ and the other with $w'$, then you accept language $(w+w')^*$.
– holf
Jun 1, 2022 at 22:26
• @holf I have updated the question with an example of a DFA where $f_M$ grows quadratically.
– Jake
Jun 1, 2022 at 22:46
• The function only depends on the language, not on the automaton. Thus the possibilities for NFA are the same as for DFA. Jun 2, 2022 at 5:28