The standard description of a finite-state machine (usually called a finite automaton) is as a 5-tuple:
.ce <{states}, {labels}, instruction-relation, start-state, {final-states}>
In Grail, however, a machine is specified simply by listing its instructions. Thus:
1 a 3 2 b 2 3 b 3 2 c 4is a list of instructions of the form <source, label, target>. Grail uses special pseudo-instructions to indicate the start and final states. Thus:
(START) |- 0 0 a 2 (START) |- 1 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)is a complete description of a machine.
In Grail, all states are designated with positive integers, and all labels are single alphabetic characters. The special pseudo-labels |- and -| are reserved for indicating the pseudo-instructions that designate that a given state is a start or final state. The pseudo-labels may be thought of as `end markers' to be matched in the input stream. The string (START) may appear only as a source state, and the string (FINAL) may appear only as a target state, and each must be accompanied by the appropriate psuedo-label (otherwise the specification of the machine is in error).
Grail permits multiple start states and multiple final states. A deterministic machine cannot have multiple start states.
The instructions in the machine need not be ordered.
Grail supports parameterizable machines. If the alphabet of your machine is not the ASCII characters, then the instruction labels will be a textual represenatation of the objects that make up the alphabet.