fmdeterm

Name

fmdeterm -- make a machine deterministic

Synopsis

fmdeterm fm

fmdeterm <fm

Description

fmdeterm computes a deterministic machine from fm, using the subset construction method. In a small number of cases, this will cause an exponential increase in the size of the machine. fmdeterm removes all unreachable states.

fm must conform to the Grail format for machines.

Examples

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

% fmdeterm nfm1
(START) |- 0
0 a 1 
1 b 1 
1 c 2 
2 d 2 
2 -| (FINAL) 

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

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

Authors