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.