Machines

This is a JavaScript implementation of DFA and NFA machines.

The module exports State, StateSet, NFAState, EndState, failState, and empty.

State

A State object behaves the same way a DFA state would. An unmapped input results in an error.

The constructor can be left empty or given a boolean of whether or not the state accepts.

var s1 = new State();
var s2 = new State(true); // accepting state

.map(input, ...states)

To create a transition from one state to another you need to map it. A state can only be mapped to another State object, but can take any input.

If multiple states are provided only the last one will be mapped.

s1.map('a', s2); // s1 on 'a' -> s2
s2.map('b', s1); // s2 on 'b' -> s1

s1.map(0, s1); // s1 on 0 -> s1

.unmap(input)

To remove a transition you need to unmap it.

s1.unmap(0);

.hasTransition(input)

You can also check if a state has a transition on an input.

.transition(...input)

You can transition to another state on a single input or multiple inputs at once.

If a given input is not mapped an error will be thrown.

var state = s1;

state = state.transition('a'); // s1 -> s2
state = state.transition('b'); // s2 -> s1

state = state.transition('a', 'b'); // s1 -> s2 -> s1

state = state.transition('c'); // throws an error!

.accepts([override])

You can check if a state accepts, or override it to accept or fail.

s2.accepts(); // true
s2.accepts(false); // s2 no longer accepts, returns false
s2.accepts(); // false

StateSet

A state set is a set of states that always consists of more than one state. It inherits the same interface and behaves the same way, with the additional functionality of being iterable.

Initializing a state set with a single state returns the state. If only one state can transition on a given input that state is returned, and if multiple states can transition a new state set is returned.

A state set can be initialized with any number of states or iterable objects containing states.

var s1 = new State();
var s2 = new State(true);

s1.map(1, s2);
s2.map(1, s1);

s1.map(2, s1);
s2.map(2, s1);

new StateSet(s1) === s1; // true

var ss = new StateSet(s1, s2);
ss.accepts(); // true

ss.transition(1); // {s1, s2} -> {s1, s2}
ss.transition(2); // {s1, s2} -> s1

for(var state of ss) {
  state === s1 || state === s2; // true, true
}

NFAState

An NFA state behaves like a DFA state, but an unmapped input takes it to a fail state. NFA states automatically transition on an empty input and return a state set if a transition leads to multiple states.

All NFA states fail to the same fail state.

var s1 = new NFAState();
var s2 = new NFAState();
var s3 = new NFAState(true);

s1.map(empty, s3).map('a', s2);
s3.map('a', s3).map('b', s2);

s1.transition('a');      // s1 -> {s1, s3} -> {s2, s3}
s1.transition('a', 'b'); // s1 -> {s1, s3} -> {s2, s3} -> s2
s1.transition('a', 'c'); // s1 -> {s1, s3} -> {s2, s3} -> fail state

EndState

An end state cannot be mapped and always transitions to itself.

var s1 = new NFAState();
var acceptState = new EndState(true);

s1.map('a', acceptState);

var state = s1;
state = state.transition('a'); // s1 -> acceptState
state = state.transition('b'); // acceptState -> acceptState

failState

A failState is a special end state that all NFA states fail to. It cannot be made into an accept state.

var NFAState = machines.NFAState;
var failState = machines.failState;

var s1 = new NFAState();

s1.transition(42) === failState; // true

empty

empty is a symbol used to represent the empty string transitions on an NFA machine.

var empty = machines.empty;
var NFAState = machines.NFAState;

var s1 = new NFAState();
var s2 = new NFAState();

s1.map(empty, s2).map('a', s1);
s2.map('a', s2);

s1.transition('a'); // s1 -> {s1, s2} -> {s1, s2}

MichaelTheriot/js-machines