🚀 go-pugleaf

Date:         28 Sep 1987 10:53:28-EDT (Monday)
From: 'Steve' Stevenson <GATECH!HUBCAP!STEVE@mcnc.org>
Subject:      Re: Minimal number of states for finite state machine

in article <C102.THEORYNT@ibm.com>, steve@hubcap.clemson.EDU ("Steve" Stevenson)
>
> Is there an efficient algorithm for converting a finite state machine into
> an equivalent machine with a minimal number of states? You may choose the
> objective function.
     
Unfortunately, the original posting was unclear as to what
I wanted.  I'm looking for the absolute minimum and hence either deterministic
                               ^^^^^^^^^^^^^^^^
or nondeterministic, whichever is smaller.  The below seems to answer the
query.  Thanks to all who responded.
     
     
>If the finite state machine is deterministic, there are standard,
>O(n sup 2) algorithms for state minimization; see Hopcroft and Ullman,
>"Introduction to Automata Theory, Languages, and Computation,"
>Addison-Wesley, 1979.  If the finite state machine is nondeterministic,
>the proble is PSPACE-complete;
>see Garey and Johnson, "Computers and Intractability," W.H. Freeman, 1979.
>
>David Johnson, AT&T Bell Laboratories
     
--
Steve (really "D. E.") Stevenson           steve@hubcap.clemson.edu
Department of Computer Science,            (803)656-5880.mabell
Clemson University, Clemson, SC 29634-1906