mdfa

    0.9.1 • Public • Published

    mdfa

    A Determinitic Finite Automata (DFA) implementation based on a monad implementation. mdfa

    About

    The motivation for implementing this module was to develop a DFA implementation based on the monad programming structure.

    Installation

    npm install mdfa
    

    Module Usage

    Define the desired DFA in a Javascript Object.

    For Example the following DFA:

    /*
    
    This DFA accepts the binary input which has an even number of zeros
    
    states: S1, S2
    alphabet: 0, 1
    start: S1
    accept: S1
    transition table:
    |---|---|----|
    |   | 0 |  1 |
    |___|___|____|
    | S1| S2| S1 |
    |___|___|____|
    | S2| S1| S2 |
    |___|___|____|
    
    */
    
    

    should be defined as:

    var dfaDefinition = {
        states: ['S1', 'S2'],
        alphabet: ['0', '1'],
        transition: {
            'S1': {
                '0': 'S2',
                '1': 'S1'
            },
            'S2': {
                '0': 'S1',
                '1': 'S2'
            }
        },
        start: 'S1',
        accept: ['S1']
    };
    

    Then the DFA object can be created:

    var createDfa = require('mdfa').create;
    var dfa = createDfa(dfaDefinition);
    

    One or more character input can be given to the DFA object using the step('string') method:

    dfa.step('0').step('1001').step('1000000').step('0')
    

    The current state can be accessed with the then(callback) method:

    dfa.then(function (result) {
        console.log('current state: ', result.state);
    });
    

    To see if the DFA accepts the current state the then(callback) method can be used:

    dfa.then(function (result) {
        console.log('isAccepted: ', result.isAccepted);
    });
    

    The step('string') and then(callback) methods are chainable:

    dfa.then(print)
       .step('0')
       .then(print)
       .step('0')
       .then(print)
       .step('1')
       .then(print)
       .step('0100')
       .then(print)
       .step('0')
       .then(print);
    
    // helper method to print the current state
    function print(result) {
        console.log('current state: ', result.state);
        console.log('accept: ', result.isAccepted);
    }
    

    Running the tests

    From inside the mdfa project folder run:

    npm install
    

    and then

    npm test
    

    Running the example

    Copy and Paste the examples/dfa_even_zeros.js file to your current folder.

    Install the mdfa module (npm install mdfa) if you have not already installed it.

    Run: node dfa_even_zeros.js

    The example demonstrates the module's usage by creating and running a DFA, which accepts the binary input with even number of zeros.

    Install

    npm i mdfa

    DownloadsWeekly Downloads

    1

    Version

    0.9.1

    License

    Public Domain

    Last publish

    Collaborators

    • pmatzavin