fmcomp

Name

fmcomp -- compute the completion of a machine

Synopsis

fmcomp fm

fmcomp <fm

Description

fmcomp computes the completion of fm and writes the result on the standard output.

fm must conform to the Grail format for machines.

A complete machine is one in which every state has a instruction on every symbol in the alphabet. fmcomp completes its input by creating a new `sink' state that is used as the target of any missing instructions in the input machine.

The alphabet used for completion is the set of symbols that appear on instructions of the machine.

Examples

% cat dfm1
(START) |- 0
0 a 1
1 b 2
2 -| (FINAL)

% fmcomp dfm1
(START) |- 0
0 a 1
1 b 2
0 b 3
2 a 3
2 b 3
1 a 3
3 a 3
3 b 3
2 -| (FINAL)


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

% fmcomp <nfm2
(START) |- 1
1 a 2
1 a 3
1 a 4
2 a 5
3 a 5
4 a 5
5 a 5
2 -| (FINAL)
3 -| (FINAL)
4 -| (FINAL)

Authors