1
$\begingroup$

Suppose I am given a finite state automaton A and a number n which should be thought of as much smaller than the number of states of A. Is there a good algorithm to find all (deterministic) finite state automata with at most n states such that either

  1. the language of the new automaton contains the language of A, or

  2. the language of the new automaton is contained in the language of A.

Really this is two problems. The goal is to find small automata that might give insight into huge automata.

$\endgroup$
2
  • $\begingroup$ I don't think this approach can give really useful information about what an automaton looks like. Indeed, If you are only interested in whether one language contains or is contained in another, just take n=1: in the former case consider the automaton with only one initial and final state with all possible loops on that state (and so the language in that of all strings on the alphabet), in the latter the automaton with only one initial state and none final (in this case the language is the empy set). $\endgroup$
    – user6530
    Commented Apr 19 at 20:46
  • $\begingroup$ Well, I wouldn’t use n=1. The hope is that one of many automata found could give insight $\endgroup$ Commented Apr 19 at 20:49

1 Answer 1

0
$\begingroup$

Probably what you are looking for is something like this:

"An n log n Algorithm for Hyper-Minimizing States in a (Minimized) Deterministic Automaton"

and

"Hyper-minimizing minimized deterministic finite state automata"

Hyper-minimization tries to reduce the number of states of an automaton beyond the limits of classical minimization: the purpose is, given an automaton $A$, to obtain an automaton $A'$ such that the symmetric difference between the languages recognized by the two automata is finite.

The algorithm presented in the second paper is also optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. Moreover, the authors prove that there is no upper bound on the number of states saved by hyperminimization. I.e., for each $m \le n$, there exists a regular language $L$ such that its minimal automaton has exactly $n$ states, but for which the hyper-minimized automaton (which is unique) has exactly $m$ states.

Anyway, note that is some cases the minimal and the hyperminimal automaton must coincide. Consider the language $L = \{1^k \mid k \mod n = 0\}$. It is obvious that the minimal automaton accepting $L$ has $n$ states (it's cycle counting modulo $n$, where the only accepting state is the initial state): it is easy to convince oneself that this automaton is also hyper-minimized.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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