A simple implementation of a dynamic finite state machine represinting an instance of a DFA (deterministic finite automata)
npm install dfa-machineA simple implementation of a dynamic finite state machine represinting an instance of a DFA (deterministic finite automata)
Install dfa-machine using npm with the command $ npm install dfa-machine --save
Any deterministic finite automata is defined by five tuples (Q,Σ,q0,δ,F) where:
- Q: The set of all states
- Σ (sigma): The set of all accepted inputs
- q0: The initial or starting state
- δ (delta): The transition function δ: Q X Σ ⟶ Q
- F: The set of final/accepted states
dfa-machine uses the same concept and implements it in javascript as follows:
The constructor of the DFA accpets two arguments:
1. sigma: an array of all accepted inputs
The current version supports inputs of the types String, Number, and Boolean only
2. machine object: an object describing initial state, final state(s), all states, and the trnsition functions/course for each state.
- The key initial must be present and have the value of a string represinting the name/key of the initial state which will be provided in the states object.
- The key final must be present and have the value of an array describing the states which will be considered accepted as a final states for a given string to be validated.
- The key states must be present and have the value of an object describing each state as a key (including but not limited to the initial and final states).
- states key must have the value of an object such as {on: {input1: 'next-state', input2: 'next-state', ...etc}} which will describe the transition function for each state while reading all inputs to be applied.
``js`
const DFA = require('dfa-machine');
In this example we will create a dfa on Σ = {0,1} that accepts strings of length greater than 0 with an even number of 1s which described in the below figure.
Our states:
- q0: The initial state. It represents either an empty string or a string with no 1s in it _(non-final)_.1
- q1: Represents an odd number of s _(non-final)_.1
- q2: Represents an even number of s _(final)_.
With that in mind we will setup our DFA instance as follows:
`js
const sigma = [0, 1];
const machineObj = {
initial: 'q0', // q0 is the key-name of the initial state provided in states object['q2']
final: ['q2'], // is the key-name(s) of the states for the machine to consider final/acceptable to end with (which must be present in states key below).on
states: {
q0: { on: { 0: 'q0', 1: 'q1' } }, // the object will describe the course for the transition function to follow as when recieving input 0 while the state is q0 the next state will be q0
q1: { on: { 0: 'q1', 1: 'q2' } },
q2: { on: { 0: 'q2', 1: 'q1' } },
},
};
const dfa = new DFA(sigma, machineObj);
dfa.validate('1101101001').status; // Valid
// OR
dfa.validate('1101101001');
dfa.status; // Valid
``
MIT