Convert NFA to DFA Online
Transform Non-Deterministic Finite State Automata (NFAs) to Deterministic Finite State Automata (DFAs) via the Subset Construction Algorithm (aka "subset algorithm") described in Compilers: Principles, Techniques, and Tools (aka the Dragon Book) and Sipser's Introduction to the Theory of Complexity.
Specify your NFA with the following, occasionally arbitrary, requirements:
- Free edges are specified as "" (the empty string). Note: free edges are also called ε-edges (epsilon-edges) in most textbooks (e.g. Aho and Sipser) or λ-edges (lambda-edges) by Fischer & Leblanc.
- Node 0 is always the start state.
- Node labels are exclusively numeric.
- But, because of JSON's nature, you have to quote the numbers. Sorry. I didn't make it an array, because some nodes lack outgoing edges, and being explicit is less hassle than playing count-the-commas.
For more details, and a tutorial in the form of a well-formed example, check out the sidebar! →