4
$\begingroup$

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 $$\binom n2 = \begin{cases}\frac{n^2-n}2 & n \geq 2 \\ 0 & n < 2\end{cases}$$
Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Since you can do $\Sigma^*$ with a DFA having one state, I do not think restricting the number of states is relevant. $\endgroup$
    – holf
    Jun 1, 2022 at 20:10
  • 1
    $\begingroup$ @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. $\endgroup$
    – Jake
    Jun 1, 2022 at 20:54
  • $\begingroup$ 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')^*$. $\endgroup$
    – holf
    Jun 1, 2022 at 22:26
  • 1
    $\begingroup$ @holf I have updated the question with an example of a DFA where $f_M$ grows quadratically. $\endgroup$
    – Jake
    Jun 1, 2022 at 22:46
  • 1
    $\begingroup$ The function only depends on the language, not on the automaton. Thus the possibilities for NFA are the same as for DFA. $\endgroup$
    – Emil Jeřábek
    Jun 2, 2022 at 5:28

1 Answer 1

Reset to default
9
$\begingroup$

(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"; or Andrew Szilard, Sheng Yu, Kaizhong Zhang, and Jeffrey Shallit. "Characterizing regular languages with polynomial densities". In MFCS, 1992. (unfortunately not available in open access)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.