How about describe a native object for state machines to extends Generator?

💡 Ideas
1

As we all know, the Generator object is returned by a generator function and it conforms to both the iterable protocol and the iterator protocol.

And according to this feature, we can describe a state machine like what mentioned here:

         E      ;      L
L: -> 0 ---> 1 ---> 2 ---> 3
      |                    ^
      |         ε          |
      ----------------------

function* machine() {
    // the start of state
    let state = 0;
    let action;

    // simple prev checker
    const _next = (prev, val) => state === prev ? val : state;

    for (;;) {
        /**
         * get the initial state, and read "action"
         * passed by `Generator.prototype.next()` each time
         */
        action = yield state;
        state = _next.apply(0, ({'E': [0, 1], ';': [1, 2], 'L': [2, 3], 'ε': [0, 3]})[action]);

        // the end of state
        if (state === 3) return state;
    }
}

const generator = machine();
generator.next(); // need to call next at first for initializing states

generator.next('E'); // => {value: 1, done: false}
generator.next(';'); // => {value: 2, done: false}
generator.next('L'); // => {value: 3, done: true}

const generator = machine();
generator.next(); // need to call next at first for initializing states

generator.next('ε'); // => {value: 3, done: true}

And then, I have an idea about describing a native object like State which extends Generator and simplify the constructing way like this:

const state = new State({'E': [0, 1], ';': [1, 2], 'L': [2, 3], 'ε': [0, 3]}, /* startState */0, /* endState */3);
state.next(); // => {value: 0, done: false};
state.next('E'); // => {value: 1, done: false}
state.next(';'); // => {value: 2, done: false}
state.next('L'); // => {value: 3, done: true}
2

You'll find it easier to not use a generator for that, but to just inherit from Iterator.prototype (which you can get just as easily from Object.getPrototypeOf(Object.getPrototypeOf([].entries()))).

Generators aren't the primitive - state machines are. And you'll find it way easier to build them if you start from a lower level of abstraction.

3

We can take an advantage from generators, which has implemented the done state for us. BTW, I have wrapped it as a simple library: GitHub - aleen42/state: A simple implementation of state machines in JavaScript with Generator.

4

First of all, your format of the transition table is severely limited. For example, it cannot describe the state machine matching regex /ABBA/, because you need two different transitions for 'A': one from the start state to "expecting BBA state", and another for "after ABB state" to the final state.

You need a 3-dimensional table: one dimension for the current state, one for the incoming symbol, one for the next state.

Second, I think it would make sense to have the start and end states in the transition table, rather than separate arguments, and if we use states numbered from 0 to N, and limit ourselves to a single final state, we can encode the transition table in an array and simply say startState=0 and finalState=length.

So for matching /ABBA/ you'd have:

transitions = [ {A:1}, {B:2}, {B:3}, {A:4} ]

Your example suggests you want to stay in the current state if you receive an unexpected symbol. That can be achieved by adding a default transition on empty string. For your example you'd have:

transitions = [ {'': 0, 'E': 1, 'ε': 3}, {'': 1, ';': 2}, {'': 2, 'L': 3} ]

You can do that with a generator function similar to the first one you wrote:

function* machine(transitions) {
    const state = 0;
    const defaultAction = yield;
    let current = transitions[0];
    while (state !== transitions.length) {
        const action = yield state;
        state = current[action];
        if (state === undefined) {
            if (defaultAction === undefined) return false;
            state = current[defaultAction];
            if (state === undefined) return false;
        }
        current = transitions[state];
    }
    return true; // successfully reached final state
}

And you call it like:

const transitions = [ {'': 0, 'E': 1, 'ε': 3}, {'': 1, ';': 2}, {'': 2, 'L': 3} ]
const state = machine(transitions);
state.next(''); // initialize defaultAction => {value: undefined, done: false};
state.next('E'); // => {value: 0, done: false}
state.next(';'); // => {value: 1, done: false}
state.next('L'); // => {value: 2, done: false}
state.next(''); // => {value: true, done: true}

edit: I've just realized that I made the same mistake as you in the example:

This is not how it would work. When you send L into the generator, what you get back is the previous state, i.e. {value: 2, done: false}.