<p>(Note: this answer only concerns the asymptotic regimes of these functions, not a precise characterization of the exact functions that are possible.)</p>
<p>It is known that, for any regular language, your function either grows exponentially, or grows polynomially. In the latter case, the language is called <em>sparse</em> (or <em>polynomially bounded</em>), and there is a characterization of the shape of the DFAs of polynomially bounded DFAs: essentially, it consists of a DAG of connected components and the transitions within each connected component, if any, must form a single cycle.</p>
<p>The degree of the polynomial intuitively corresponds to the maximal number of connected components with a cycle that can be seen on a path on the DAG of connected components.</p>
<p>If the function is O(1) then this is called a <em>slender language</em> and if the function is upper bounded by 1 (at most one word per length) then this is called a <em>thin language</em>.</p>
<p>For more information, see Chapter XII, Section 4.2, of Jean-Eric Pin's &quot;<a href="https://www.irif.fr/%7Ejep/PDF/MPRI/MPRI.pdf" rel="noreferrer">Mathematical Foundations of Automata Theory</a>&quot;; or Andrew Szilard, Sheng Yu, Kaizhong Zhang, and Jeﬀrey Shallit. &quot;Characterizing regular languages with polynomial densities&quot;. In MFCS, 1992. (unfortunately not available in open access)</p>

CC BY-SA 4.0
2022-06-02T06:18:37.987Z
2022-06-02T06:18:37.987Z
Antoine Amarilli 'a3nm'
<p>Let <span class="math-container">$M$</span> be an arbitrary DFA. For each <span class="math-container">$n \in \mathbb{N}$</span>, let <span class="math-container">$f_M(n)$</span> be the number of words of length <span class="math-container">$n$</span> accepted by <span class="math-container">$M$</span>. Then, consider the set of all such <span class="math-container">$f_M$</span> for all DFAs <span class="math-container">$M$</span>.</p>
<p>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 <span class="math-container">$M$</span>, or if we make <span class="math-container">$M$</span> an NFA? Any relevant information would be appreciated.</p>
<h2>Examples:</h2>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>DFA Image</th>
<th><span class="math-container">$f_M(n)$</span></th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="https://i.sstatic.net/LgoEl.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/LgoEl.png" alt="A sample DFA with quadratic growth" /></a></td>
<td><span class="math-container">$$\binom n2 
= \begin{cases}\frac{n^2-n}2 &amp; n \geq 2 \\ 0 &amp; n &lt; 2\end{cases}$$</span></td>
</tr>
</tbody>
</table>
</div>
CC BY-SA 4.0
2022-06-01T20:10:46.067Z
Since you can do $\Sigma^*$ with a DFA having one state, I do not think restricting the number of states is relevant.
holf
CC BY-SA 4.0
2022-06-01T20:54:57.757Z
@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
CC BY-SA 4.0
2022-06-01T22:26:46.303Z
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
CC BY-SA 4.0
2022-06-01T22:46:06.390Z
@holf I have updated the question with an example of a DFA where $f_M$ grows quadratically.
Jake
CC BY-SA 4.0
2022-06-02T05:28:45.980Z
The function only depends on the language, not on the automaton. Thus the possibilities for NFA are the same as for DFA.
Emil Jeřábek
CC BY-SA 4.0
2022-06-02T06:16:53.577Z
Isn’t this just all functions that can be written as $v^TM^nx$ where $v$ is a n-dimensional vector with a single $1$ and all other entries $0$, $M$ is a $n$ times $n$ matrix with $0$-$1$ entries and $x$ is a vector with $0$-$1$ entries?
daniello
CC BY-SA 4.0
2022-06-02T12:01:45.733Z
@EmilJeřábek well if you also restrict the number of states then determinism may change things.
holf
<automata-theory>
Characterization of lengths of words accepted by DFAs
Jake
# Characterization of lengths of words accepted by DFAs

(Asked by: username_0 on 2022-06-01)

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)$ |
| --- | --- |
| [A sample DFA with quadratic growth](https://i.sstatic.net/LgoEl.png) | $$\binom n2 = \begin{cases}\frac{n^2-n}2 & n \geq 2 \\ 0 & n < 2\end{cases}$$ |

**Tags:** automata-theory

> **Comments:**
> **username_1**: Since you can do $\Sigma^*$ with a DFA having one state, I do not think restricting the number of states is relevant.  
> **username_0**: @username_1 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.  
> **username_1**: 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')^*$.  
> **username_0**: @username_1 I have updated the question with an example of a DFA where $f_M$ grows quadratically.  
> **username_2**: The function only depends on the language, not on the automaton. Thus the possibilities for NFA are the same as for DFA.  
> **username_3**: Isn’t this just all functions that can be written as $v^TM^nx$ where $v$ is a n-dimensional vector with a single $1$ and all other entries $0$, $M$ is a $n$ times $n$ matrix with $0$-$1$ entries and $x$ is a vector with $0$-$1$ entries?  
> **username_1**: @EmilJeřábek well if you also restrict the number of states then determinism may change things.  

---

## 1 answers

### Answer by username_4 on 2022-06-02. Score: 9 | Accepted answer

(Note: this answer only concerns the asymptotic regimes of these functions, not a precise characterization of the exact functions that are possible.)

It is known that, for any regular language, your function either grows exponentially, or grows polynomially. In the latter case, the language is called *sparse* (or *polynomially bounded*), and there is a characterization of the shape of the DFAs of polynomially bounded DFAs: essentially, it consists of a DAG of connected components and the transitions within each connected component, if any, must form a single cycle.

The degree of the polynomial intuitively corresponds to the maximal number of connected components with a cycle that can be seen on a path on the DAG of connected components.

If the function is O(1) then this is called a *slender language* and if the function is upper bounded by 1 (at most one word per length) then this is called a *thin language*.

For more information, see Chapter XII, Section 4.2, of Jean-Eric Pin's "[Mathematical Foundations of Automata Theory](https://www.irif.fr/%7Ejep/PDF/MPRI/MPRI.pdf)"; or Andrew Szilard, Sheng Yu, Kaizhong Zhang, and Jeﬀrey Shallit. "Characterizing regular languages with polynomial densities". In MFCS, 1992. (unfortunately not available in open access)


---

