Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finite State Machine parsing

Tags:

javascript

fsm

This picture depicts finite state machine parsing "nice" string.

The question is how would it look like in JS code?

EDIT

Picture from link above:

finite state machine parsing

like image 340
DrStrangeLove Avatar asked Nov 17 '11 18:11

DrStrangeLove


2 Answers

According to wikipedia(where your link points) this refers to an "Acceptor FSM" and "By definition, the languages accepted by FSMs are the regular languages". One could say that it will be just /^nice$/.test(somestring). If this helps and you need more info on regular expressions take a look at RegExp.

like image 182
Prusse Avatar answered Sep 22 '22 06:09

Prusse


I did a little FSM work in Javascript on a project just recently. My code, adapted for the case above, looks like this - you have a factory to make the state automaton, which is just a sequence of steps it's trying to match:

function fsmAutomatonFactory(tests) {
    var step = 0;
    var state = false; // acceptance state

    return {
        testNext: function(element) {
            // matches current step
            if (tests[step].test(element)) {
                // advance step
                step++;
                return true;
            }
            // no match
            return false;
        },
        getState: function() {
            // all steps completed successfully
            return step >= tests.length
        }
    }
}

Now you can set up an automaton with a series of tests, and run the input series through it:

function fsmTest(str) {
    // set up automaton
    var tests = [
        { test: function(l) { return l == 'n' }},
        { test: function(l) { return l == 'i' }},
        { test: function(l) { return l == 'c' }},
        { test: function(l) { return l == 'e' }}
    ];
    var automaton = fsmAutomatonFactory(tests);

    // run the test letter by letter
    for (var x=0; x<str.length; x++) {
        // you could break early here if you wanted
        automaton.testNext(str[x]); 
    }
    return automaton.getState();
}

This is a lot of code for str == "nice", but it scales relatively well to more complex inputs and tests. This works for a linear pattern like your case; if you needed branching or more complex logic, you might need to implement a state transition table or other mechanism to handle transitions other than state++.

like image 28
nrabinowitz Avatar answered Sep 25 '22 06:09

nrabinowitz