Skip to content

Instantly share code, notes, and snippets.

@martinwairegi
Created March 27, 2023 05:37
Show Gist options
  • Save martinwairegi/fdb076100857569e70ecbd0ba29bee9f to your computer and use it in GitHub Desktop.
Save martinwairegi/fdb076100857569e70ecbd0ba29bee9f to your computer and use it in GitHub Desktop.
/** * 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