# Maximal minimal DFA for some language of n-bit strings

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.

• @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 May 19, 2021 at 20:49
• That helped a ton! Thank you.
– D.W.
May 19, 2021 at 20:55
• 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.
– D.W.
May 19, 2021 at 22:15
• @D.W. Many thanks again for all your help! May 20, 2021 at 2:45