arvind@utcsri.UUCP (09/29/87)
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