ON THE SYNTHESIS OF FINITE-STATE ACCEPTORS
Alan W. Biermann, Jerome A. Feldman · 1970
Two algorithms are presented for solving the following problem: given a finite-set S of strings of symbols, find a finite-state machine which will accept the strings of S and possibly some additional strings which 'resemble' those of S. The approach used is to directly construct the states and transitions of the acceptor machine from the string information. The algorithms include a parameter which enable one to increase the exactness of the resulting machine's behavior as much as desired by increasing the number of states in the machine. The properties of the algorithms are presented and illustrated with a number of examples. The paper gives a method for identifying a finite-state language from a randomly chosen finite subset of the language if the subset is large enough and if a bound is known on the number of states required to recognize the language. Finally, some of the uses of the algorithms and their relationship to the problem of grammatical inference are discussed.