fsalib

Finite State Automaton Library

Its a very simple fSA lib, with some advanced operations like:

• Clean dead and unreachable states,
• Determinism,
• Minimization,
• Union,
• Intersection,
• Subtraction,
• Negation
• toDot,
• fromJSON,
• toJSON

All operations except clean and fromJSON are non-destructive, this means that the result is a new FSA and origin FSA is unchanged.

Install

npm install fsalib --save

Use

    const FA = require("./fsa");

    const abc = new FA();
    const def = new FA();

    {
        const s = abc.getStart();
        const s1 = abc.newState();
        const s2 = abc.newState();
        const s3 = abc.newState();

        abc.setFinal(s3);

        abc.transition(s, 'a', s1);
        abc.transition(s1, 'b', s2);
        abc.transition(s2, 'c', s3);
    }

    {
        const s = def.getStart();
        const s1 = def.newState();
        const s2 = def.newState();
        const s3 = def.newState();

        def.setFinal(s3);

        def.transition(s, 'd', s1);
        def.transition(s1, 'e', s2);
        def.transition(s2, 'f', s3);
    }

    // clean a,
    abc.clean();

    // create a deterministic FSA from abc,
    const det = abc.deterministic();

    // create new minimized FSA from abc.
    const min = fa.minimize();

    // union of both FSA,
    // result (un) will acept all words that are acepted by abc or def.
    const un = abc.union(def);

    // intersect both FSA,
    // result (inter) will acept all words acepted by both FSA (abc and def).
    const inter = abc.intersect(def);
    
    // subtract abc - def,
    // result (sub) FSA will acept all words acepted by abc but not the ones acepted by def.
    const sub = abc.subtract(def);

    // negation,
    // will acepted all words  
    // it will create a FSA aceptiong all possible words
    // generated by abc alphabet except the words acepted by abc.
    const neg = abc.negation();

    // print dot (graphviz graph version)
    // handy for debug.
    console.log(abc.toDot());

    // serialize to json,
    // return a json description of the abc FSA.
    console.log(JSON.stringify(abc.toJSON()))

    // deserialize from json,
    // create a copy of abc.
    const f = (new FA()).fromJSON(abc.toJSON());

FA Fields

There is no functions to walk a FA or accept a word, instead you can access the FA fields directly.

Here is a example taken from the toJSON function:

    const transitions = [];

    // this.transitions is a Map where key is a from state
    // and value is another Map with key as symbol and values 
    // a Set of destination states (tos).
    for (let [from, symbols] of this.transitions) {
        const ss = [];
        // symbols is a Map with key symbols and value a Set of to states.
        for (let [symbol, tos] of symbols) {
            // In case FA is deterministic the tos is Set with only one element.
            ss.push([symbol, [...tos]]);
        }

        transitions.push([from, ss]);
    }

    return {
        // Final states,
        finals: [...this.finals],
        
        // all states, including final states,
        states: [...this.states],

        // the start state,
        start: this.start,

        // Symbols the FA alphabet,
        symbols: [...this.symbols],

        // FA transitions,
        transitions,

        // its the state id counter,
        // everytime a state is created we return the current ids value and 
        // increment it, for next round, messing up the ids is not a good ideia. 
        ids: this.ids
    };

More Examples

There are lot more examples/test here: https://github.com/fsvieira/fsalib/blob/master/src/fsa.test.js

Use Cases

The use cases of Finite State Automata are very large well known and document
on many sources. 

Some examples can be, regular expressions, pattern analyses/recognition, 
application/game state machines ...

With a little creativity we can found some use for a FSA, on almost any application.