fmmin

Name

fmmin -- compute the minimal machine

Synopsis

fmmin fm

fmmin <fm

Description

fmmin computes the minimal machine that accepts the same language as fm, and writes the result on the standard output. fmmin returns 0 if the input machine is non-deterministic. The machine can be made deterministic by first filtering it with fmdeterm. fmmin uses Hopcroft's partition algorithm. It removes unreachable states.

fm must conform to the Grail format for machines.

Examples

% cat dfm
(START) |- 0
0 a 1
0 b 2
1 c 1
2 c 2
1 d 3
2 d 4
3 -| (FINAL)
4 -| (FINAL)

% fmmin dfm
(START) |- 1
1 a 2
1 b 2
2 c 2
2 d 0
0 -| (FINAL)


% cat nfm2
(START) |- 1
1 a 2
1 a 3
1 a 4
2 -| (FINAL)
3 -| (FINAL)
4 -| (FINAL)

% cat nfm2 | fmdeterm | fmmin
(START) |- 1
1 a 0 
0 -| (FINAL)

Authors