DFA-lib
A JavaScript library for working with DFAs and NFAs. Used in 2015 for tools for an introductory computer science class (CS103) at Stanford.
Features
-
Parsing.
-
Various manipulations: converting NFAs to DFAs, finding minimal DFAs, taking intersections, Kleene stars, etc.
-
Equivalence counterexamples: given two automata, find strings accepted by one and not the other, if they are not equivalent.
Example
var oddb = // ends in an odd number of b's 'a' 'b' // alphabet // transition table 0: 'a': '0' 'b': '1' 1: 'a': '0' 'b': '0' '0' // start state '1' // accepting states; var evena = // contains a positive even number of a's 'a' 'b' 0: 'a': '1' 'b': '0' 1: 'a': '2' 'b': '1' 2: 'a': '3' 'b': '2' 3: 'a': '2' 'b': '3' '0' '2'; console; // 'aab' var zoz = // strings containing '010' as a substring. '0' '1' // alphabet // transition table. Note that transitions are to sets of states, and that transitions can be absent (equivalent to mapping to the empty set). 0: 0: '0' '1' 1: '0' 1: '': '0' 1: '2' // Note also that states can transition on the empty string (i.e., an epsilon transition), though it's entirely redundant in this particular automaton. 2: 0: '3' 3: 0: '3' 1: '3' '0' // set of initial states '3' // set of accepting states; console; // prints a human-readable serialization of the minimal equivalent DFA.
License
Licensed under the MIT license. If you're making public or commercial use of this library, I encourage (but do not require) you to tell me about it!