fmminrev

Name

fmminrev -- compute the minimal machine

Synopsis

fmminrev fm

fmminrev <fm

Description

fmminrev computes the minimal machine that accepts the same language as fm, and writes the result on the standard output. fmminrev can accept either a deterministic or nondeterministic machine as input. fmminrev computes the minimal machine by reversing, performing subset construction (that is, by applying fmdeterm), reversing again, and performing subset construction a final time). The result is guaranteed to be deterministic.

Machines can also be minimized by fmmin, which uses Hopcroft's partition method. fmmin and fmminrev produce isomorphic results (that is, identical up to state renumbering).

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)

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

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

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

Authors