-
-
Save martinwairegi/fdb076100857569e70ecbd0ba29bee9f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** * Simulate the NFA on a given string * @param {String} str The input string to test * @returns {Boolean} | |
Whether the NFA accepts the string or not */ simulate(str) { var current = [this.nfa[this.start]]; // | |
Current set of states for (var i=0; i<str.length; i++) { var next = []; | |
// Find all states reachable from current states with input symbol for (var state of current) | |
{ var transitions = state[str[i]]; if (transitions) { for (var s of transitions) | |
{ if (!next.includes(this.nfa[s])) { next.push(this.nfa[s]); } } } } current = next; } | |
// Check if any accept state is reachable from current states for (var state of current) | |
{ | |
if (this.end.includes(state)) | |
{ return true;} | |
} return false; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment