Finite Deterministic Cover Automata (DFCA) can be obtained from Deterministic Finite Automata (DFA) using the similarity relation. Since the similarity relation is not an equivalence relation, the minimal DFCA for a finite language is usually not unique. We count the number of minimal DFCA that can be obtained from a given minimal DFA with n states by merging the similar states in the given DFA. We compute an upper bound for this number and prove that in the worst case (for a non-unary alphabet) it is 「(4n-9+(8n+1)~(1/2))/8」!/(2「(4n-9+(8n+1)~(1/2))/8」-n+1)!. We prove that this upper bound is reached, i.e. for any which has the number of minimal DFCA obtained by merging similar states equal to this maximum.
展开▼
