fslib

Finite state transducer library. Minimalist pure C implementation. This project is mostly inspired by OpenFST library (http://www.openfst.org) by Michael Riley and Mehriar Mohri. The main focus here is performance and simplicity.

Setup

C99 compiler is required. Just run:

git clone https://github.com/c0stya/fslib.git
cd fslib && make

To run compile and run tests:

make tests

Usage

Compilation

Let's create an automaton that accepts "(01)*" regular language. We need a fscompile command:

echo  "\
0 1 0 0
1 0 1 1
0" | fscompile > automaton.t

Each line contains either transition or final state.

Transition line format:

• source state
• destination state
• input label
• output label
• (optional) weight

Final state line contains only a number of a state.

Printing

To print it just invoke fsprint command:

fsprint automaton.t

or as usual pipe:

cat automaton.t | fsprint

Composition

To compose transducers one should use the fscompose command:

fscompose aut0.t aut1.t > aut3.t

It could be done in the pipe style with more then two automata:

cat aut0.t | fscompose - aut1.t | fscompose - aut2.t > aut3.t

Warning: a proper sorting of input/output arcs could be significantly increase the performance.

Shortest path

Use fsshort command to get the a transducer with the shortest path:

fsshort automaton.t > shortest_path.t

Drawing

We could draw automaton using fsdraw command. To actually render it you need dot utility from the Graphviz package. Make sure you have Graphviz (http://www.graphviz.org) package properly installed.

To render a transducer to a png file use the following:

fsdraw automaton.t | dot -Tpng > automaton.png