HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Maximal minimal DFA for some language of n-bit strings

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dfabitlanguagestringssomeforminimalmaximal

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#140211, answer score: 3

Revisions (0)

No revisions yet.