1
$\begingroup$

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$?

$\endgroup$
12
  • 2
    $\begingroup$ I don't understand your quantification. For example, "for all $n$ such that $|L_n| = O(n^c)$" is meaningless (always true), since asymptotic notation only makes sense asymptotically. Similarly, it is always true that there exists a constant $c$ (we can take $c = 0$) such that the minimal DFA for $L_n$ has only $O(n^c)$ states. I also suspect that there is a relation between the different $c$'s appearing in the statement. $\endgroup$ Jul 11, 2022 at 9:43
  • 1
    $\begingroup$ I don't know if I understand your question correctly, but you can build the complete tree containing a state for all words in $\Sigma^{\leq n}$ and 'trim' down from all the words that you want to recognize. This tree will not have more states on each level than words you want to recognize. $\endgroup$
    – Janmar
    Jul 11, 2022 at 9:50
  • 1
    $\begingroup$ I don't see why it would not hold for $c=0$. If there are only a constant $k$ words of length $n$, it can be represented by a $k$ chains of length $n$, hence having at most $k$ states on each level. $\endgroup$
    – Janmar
    Jul 12, 2022 at 8:22
  • 1
    $\begingroup$ I believe that Janmar answered your question in the comments. $\endgroup$ Jul 12, 2022 at 15:41
  • 1
    $\begingroup$ By at most a factor of $n$ (give or take), and potentially even better. $\endgroup$ Jul 12, 2022 at 15:55

1 Answer 1

1
$\begingroup$

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.

$\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.