Finite State Machine parsing

Question

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:

Kilogram

Answer 1

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.

Brisco

Answer 2

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++.

Medea

Thanks! let's say i want to parse another word - "programmer" instead of "nice"- Should i make new tests array?? if so, how can a program make a distinction between these arrays?? do i need tests arrays for every word i'd like to parse?? – Kilogram

Well, this code was designed for more complex tests (I'm using it to look for repeated patterns in web content, with various tests including jQuery selector matching and regex). So yes, each test suite - essentially the logic of different FSMs - would have its own set of tests. You could easily make a function to produce tests automatically for a new string, or a series of regexps, or what have you. – Medea