contents index next

18. fsa_io: Reading and Writing Finite State Automata

This module provides predicates to read and write finite automata in a variety of formats. The defaul format for reading is determined by the global variable *read*. The default format for writing is determined by the global variable *write*.

The following formats are available both for reading and writing:

For writing, the following additional formats are available:

The normal format is the internal format used in FSA6. The module fsa_data provides a consistent interface to this format.

Here is a table indicating the relative speed of the standard input and output formats:

format      compact    fast     normal
writing          20       1          4
reading           5       1          4

Here is a table indicating the relative size of the standard input and output formats (measured in bytes):

compact    fast     normal
      1     1.8        1.6

18.1. Description of I/O formats

This section describes the various I/O formats.

18.1.1. The normal format

In the normal format, a finite automaton is a single Prolog term

fa(Symbols,States,Starts,Finals,Transs,Jumps).

Symbols is a term r(Sig) (for recognizers) or t(SigD,SigR) for transducers. Here *Sig*, *SigD*, SigR are the predicate modules.

States is an integer indicating the number of states in the automaton.

Starts is an ordered list of integers indicating the start states of the automaton.

Finals is an ordered list of integers indicating the final states of the automaton.

Transs is an ordered list of triples trans(A,B,C) where A and C are integers indicating source and target state, and B is a symbol (recognizers) or a symbol pair InSym/OutSym (transducers). InSym is a symbol or the empty list. OutSym is a symbol or a (possibly empty) list of symbols.

Jumps is an ordered list of pairs jump(A,B) where A and B are integers indicating source and target state. This implies there is an epsilon transition from A to *B*.

18.1.2. The old format

In the old format a finite automaton is given as a Prolog program. The automaton is defined by clauses for the predicates:

Note that in this format states can be are arbitrary ground Prolog terms (these will be converted to integers). In the case of transducers, Sym is a pair Left/Right. The empty list [] is used to indicate the empty string. In the case of sequential transducers, Right must be a list of symbols.

18.1.3. The compact format

The compact format fairly closely follows the normal format. See the documentation on the normal format in the fsa_data module for more information. In this format a file is an ordinary text file. The format is intended to be used for machines only, and is not very helpful for human consumption.

Example:

fsa write=compact -r '[class(a..f),{g,h}]'
fsa6
r
fsa_preds
3
0
1
0       in([a,b,c,d,e,f])       2
2       g       1
        h       1

18.1.4. The fast format

The fast format uses the same Prolog term representation as the normal format, except that library(fastrw) is used to read and write the Prolog term. This implies that reading and writing of automata in this format is very fast; the disadvantage is that fast is a binary format and therefore cannot be (easily) treated by other programs.

18.2. List of Predicates

This section lists the predicates defined by this module.

18.2.1. copy_fa(+File0,+File1).

The automaton in File0 is copied to File1. Useful to convert between different formats, by setting the read and write global variables.

18.2.2. fsa_read_file([+Format,]+File,?Fa)

Fa is read from File. If Format is unspecified the value of the global variable read is taken as the input format.

18.2.3. fsa_write_file([+Format,]+File,+Fa)

Fa is written to File. If Format is unspecified the value of the global variable write is taken as the input format.

contents index next