State Complexity of DFAs for Restricted Languages

Question

Let $\Sigma$ be a finite alphabet. All strings below are over $\Sigma$.

Definitions: If a string $s = vw$, then $v$ is a $\textit{prefix}$ of $s$ and $w$ is a $\textit{suffix}$ of $s$.
For a language $L \subseteq \Sigma^*$, define $L_n \subseteq L$ to be the set of strings in $L$ of length $n$: $L_n = \{s \mid s \in L \; \textrm{and} \; |s| = n \}$.
Since $L_n$ is finite, it can be recognized by a deterministic finite-state automaton (DFA) $M_{L,n}$ that is minimal and acyclic.
A $\textit{level}$ of an acyclic DFA is the set of all states at the same depth as measured from the start state.

We are given the following constraint on $L$:

$$ | L_n | = O(n^c) $$ where $c$ is a constant that depends on $L$ but not on $n$.

Now if we take the set of all prefixes of a certain length $d$,

$$ S_{n,d} = \{ v \mid vw \in L_n, |v| = d \} $$

$S_{n,d}$ is also similarly bounded:

$$ | S_{n,d} | = O(n^c) $$

So even if, in the worst case, all strings in the $S_{n,d}$ are Myhill-Nerode distinguishable from each other, there are therefore only $O(n^c)$ states at depth $d$ in $M_{L,n}$.

So can we conclude that: given a language $L$ such that $ | L_n | = O(n^c) $ where $c$ is a constant, the minimal acyclic DFA that recognizes the subset $L_n \subseteq L$ has only $O(n^{k})$ states for some fixed $k$?

Answer 1

If $L_n$ contains $m$ words, then it is accepted by a DFA having at most $nm + 2$ states. The DFA has a state for each prefix of each word in $L_n$, together with a sink state. In particular, if $|L_n| = O(n^c)$, then the state complexity of $L_n$ is $O(n^{c+1})$.

The following example shows that a loss of a factor of $n$ is inevitable. Consider the language $L$ over $\{0,1\}$ of all words containing at most $\ell$ runs. For example, if $\ell = 2$ then the language is $0^*1^* + 1^*0^*$. For this language, $|L_n| = \Theta(n^{\ell-1})$ while the state complexity of $L_n$ is $\Theta(n^\ell)$.

If $|L_n| = \Theta(n^c)$ for some regular language $L$ then $c \in \mathbb{N}$, so the example above covers all possible cases.