Deterministic Finite Automata to search for the substrings '01', '010' and 'hallo'

fgdi-dfautomaton.js

#!/usr/bin/node

// A = (alphabet, states, q0, Delta, Z)

//--> Deterministic Finite Automaton

function Automaton(alphabet, Q, q0, Delta, Accept) {
  this.alphabet = alphabet;
  this.Q = Q;
  this.q0 = q0;
  this.Delta = Delta;
  this.Accept = Accept;
}
Automaton.prototype.delta = function(q, a) {
  if (this.alphabet.indexOf(a) == -1) return false;
  if (this.Q.indexOf(q) == -1) return false;
  
  for (var i in this.Delta) {
    if (this.Delta[i][0] == q && this.Delta[i][1] == a) return this.Delta[i][2];
    if (this.Delta[i][0] == q && this.Delta[i][1] == '*') return this.Delta[i][2];
  }
  return false;
}
Automaton.prototype.run = function(word) {
  var state = this.q0;
  for(var i in word) {
    state = this.delta(state, word[i]);
  }
  return state;
}
Automaton.prototype.check = function(word) {
  var endState = this.run(word);
  return (this.Accept.indexOf(endState) > -1);
}


//--> Test Automatons

//teilwort 01
var A = new Automaton(
  /* alphabet: */ ['0', '1'],
  /* states: */ ['S0', 'S2', 'S1'],
  /* q0: */ 'S0',
  /* Delta: */ [
    ['S0', '0', 'S2'],
    ['S0', '1', 'S0'],
    ['S2', '0', 'S2'],
    ['S2', '1', 'S1'],
    ['S1', '0', 'S1'],
    ['S1', '1', 'S1']
  ],
  /* Z: */ ['S1']
);

//teilwort 010
var B = new Automaton(
  /*alphabet: */ ['0', '1'],
  /*states: */   ['S0', 'S1', 'S2', 'S3'],
  /*q0: */       'S0',
  /*Delta: */    [
    ['S0', '0', 'S1'],
    ['S0', '1', 'S0'],
    ['S1', '0', 'S1'],
    ['S1', '1', 'S2'],
    ['S2', '0', 'S3'],
    ['S2', '1', 'S0'],
    ['S3', '0', 'S3'],
    ['S3', '1', 'S3']
  ],
  /*Z: */        ['S3']
);

//teilwort hallo
var C = new Automaton(
  /*alphabet: */ 'abcdefghijklmnopqrstuvwxyz '.split(''),
  /*states: */   ['S0', 'S_H', 'S_A', 'S_L1', 'S_L2', 'S_O', 'S1'],
  /*q0: */       'S0',
  /*Delta: */    [
    ['S0', 'h', 'S_H'],
    ['S0', '*', 'S0'],
    
    ['S_H', 'a', 'S_A'],
    ['S_H', 'h', 'S_H'],
    ['S_H', '*', 'S0'],
    
    ['S_A', 'l', 'S_L1'],
    ['S_A', 'h', 'S_H'],
    ['S_A', '*', 'S0'],
    
    ['S_L1', 'l', 'S_L2'],
    ['S_L1', 'h', 'S_H'],
    ['S_L1', '*', 'S0'],
    
    ['S_L2', 'o', 'S_O'],
    ['S_L2', 'h', 'S_H'],
    ['S_L2', '*', 'S0'],
    
    ['S_O', '*', 'S1'],
    ['S1', '*', 'S1'],
  ],
  /*Z: */        ['S_O', 'S1']
);

//--> Test Words
var words = [
  '11100000', '11111', 'hallo', '11111', '000', '01', '10', 
  '001101001', '0000000', '000XX', 'halle hall', 'halli hallo welt'
];

log("Word", "endState A", "accept A", "endState B", "accept B", "endState C", "accept C");
for(var i in words) {
  var w = words[i];
  log(w, A.run(w), A.check(w), B.run(w), B.check(w), C.run(w), C.check(w));
}

//--> Test Output
/*
| Word                | endState A | accept A   | endState B | accept B   | endState C | accept C    |
| 11100000            | S2         | false      | S1         | false      | false      | false       |
| 11111               | S0         | false      | S0         | false      | false      | false       |
| hallo               | false      | false      | false      | false      | S_O        | true        |
| 11111               | S0         | false      | S0         | false      | false      | false       |
| 000                 | S2         | false      | S1         | false      | false      | false       |
| 01                  | S1         | true       | S2         | false      | false      | false       |
| 10                  | S2         | false      | S1         | false      | false      | false       |
| 001101001           | S1         | true       | S3         | true       | false      | false       |
| 0000000             | S2         | false      | S1         | false      | false      | false       |
| 000XX               | false      | false      | false      | false      | false      | false       |
| halle hall          | false      | false      | false      | false      | S_L2       | false       |
| halli hallo welt    | false      | false      | false      | false      | S1         | true        |
*/



//--> Helper Functions

function log() {
  var q = "";
  for(var i in arguments) q+= '| '+(arguments[i]+'                          ').substr(0,i>0?11:20);
  console.log(q+' |');
}