Table of Contents

Name

minimize - minimize an automaton in format of Gertjan van Noord fsa program

Synopsis

minimize [ options ] [ file ]

Description

minimize minimizes a deterministic finite state automaton. The automaton may contain cycles. For each state in the automaton, there must be a path from the initial state to that state, and from that state to any of the final states. The default minimization algorithm is the incremental minimization algorithm by Bruce Watson with modifications by Jan Daciuk. The modifications tranform the original exponential algorithm into an (almost) quadratic one. Other algorithms are available: Brzozowski, Aho-Sethi-Ullman, Hopcroft-Ullman, and Hopcroft. Depending on compile options, the program may print partially minimized automata (only for the incremental algorithm), execution time, and other statistics. Statistics are printed as comments in the output automaton. They are in separate lines beginning with a percent sign, and an exclamation mark. The input is taken from the file specified in the command line, or from the standard input. The output is on the standard output. Both input and output are in format of Gertjan van Noord's fsa program.

Options

-A
use Aho-Sethi-Ullman minimization algorithm. This option is available when the program is compiled with -DASU_ALG. The default minimization algorithm is the incremental one.
-H
use Hopcroft minimization algorithm. This option is available when the program is compiled with -DHOPCROFT. The default minimization algorithm is the incremental one.
-U
use Hopcroft-Ullman minimization algorithm. This option is available when the program is compiled with -DHOPUL. The default minimization algorithm is the incremental one.
-r
stop after having read an automaton (i.e. the input data).
-v
prints the compile options used during compilation of the program.
file
input file in format of Gertjan van Noord's fsa program. If not present, standard input is used.

Exit Status

  1. OK
  2. the automaton is not deterministic.
  3. syntax error.
  4. error in the algorithm (well, this will never happen, of course).
  5. unknown error. This includes memory allocation errors.

See Also

genaut(1) , inflate(1) . Also see the page http://www.eti.pg.gda.pl/~jandac/minim.html

Bugs

Send bug reports to the author: Jan Daciuk, jjaannddaacc@eti.pg.gda.pl (remove stuttering)

Table of Contents