4
$\begingroup$

Notation: $M$ is a DFA; $L(M)$ is the language accepted by $M$; $\min(M)$ is the minimal automaton equivalent to $M$ derived from a minimization algorithm such as the Hopcroft algorithm; and $|M|$ is the size of $M$: the number of states in $M$.

We are given the alphabet $\{0,1\}$ and some $n \in \mathbb{N}$.

Let's define some sets to set up the question.

$$ A = \{M \mid L(M) \subseteq \{0,1\}^n\}$$

So $A$ is the set of all automata that accept some language whose words are composed of $n$-bit binary strings. My intention here is also to require that all members of $A$ reject strings of other lengths. Building from this, consider

$$ A_{\min} = \{ \min(M) \mid M \in A \} $$

So $A_{\min}$ is the set of all minimized automata from $A$. Building further, let

$$ x = \max \{ |M| \mid M \in A_{\min}\} $$

So $x$ is the size of the largest automaton from $A_{\min}$. Now we can specify the automaton or automata we're looking for:

$$S = \{ M \mid M \in A_{\min} \, \, \text{and} \, \, |M| = x \} $$

How would one go about constructing a member (or members) of $S$? Any will do, but simpler constructions are preferred.

My initial naive attempt to do this failed. I tried building it up by induction, starting from a basis state which had two states: an accepting state and a non-accepting state. For the inductive step, I tried to build a binary tree composed of two different subtrees built from the previous step. This failed because minimization still merged common subtrees together.

$\endgroup$
4
  • $\begingroup$ @D.W. Thanks for your ongoing help and patience with this question. I've substantially rewritten the question to make things more precise. To address your specific questions: "over" is formalized by set $A$. $A$ also addresses your first two questions. Your third question is addressed by set $S$. Your final question is addressed by $min(M)$ in the notation section. Please let me know what other improvements I can make so this question can be reopened. Many thanks $\endgroup$ – ShyPerson May 19 at 20:49
  • 1
    $\begingroup$ That helped a ton! Thank you. $\endgroup$ – D.W. May 19 at 20:55
  • 1
    $\begingroup$ Here's a construction that might get close to the right asymptotics: let $\Sigma=\{0,1\}^{\lg n}$; there's an isomorphism $\Sigma^{n/\lg n} \to \{0,1\}^n$; then consider the language of all words $w$ over $\Sigma^{n/\lg n}$ such that at least one $s \in \Sigma$ does not appear in $w$, i.e., $L=\{w \in \Sigma^{n/\lg n} \mid \exists s \in \Sigma . w \in (\Sigma \setminus \{s\})^{n/\lg n}\}$. Then by cs.stackexchange.com/q/3381/755, the minimal DFA for $L$ has at least $2^{n/\lg n}$ states. It's easy to see that $x \le n \cdot 2^n$ states. $\endgroup$ – D.W. May 19 at 22:15
  • $\begingroup$ @D.W. Many thanks again for all your help! $\endgroup$ – ShyPerson May 20 at 2:45
2
$\begingroup$

Your question is solved in Cezar Câmpeanu and Wing Hong Ho, The Maximum State Complexity for Finite Languages, Corollary 10.

$\endgroup$
2
  • $\begingroup$ Thanks! If I have follow-up questions, do I ask them here or in a new question? $\endgroup$ – ShyPerson May 20 at 3:18
  • $\begingroup$ Depends on the question. $\endgroup$ – Yuval Filmus May 20 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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