Skip to content

Instantly share code, notes, and snippets.

Created March 27, 2023 05:37
What would you like to do?
/** * 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