# 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!

## Input NFA as JSON

/* Comments like me are ignored */ { /* State 0 (S0) has epsilon-edges to S3 & S5 */ "0" : {"=" : 1, "" : [3,5]}, "1" : {"=" : 2, "ACCEPT" : "assignment"}, "2" : {"ACCEPT" : "comparison"}, "3" : {"D" : 4}, "4" : {"D" : 4, "ACCEPT" : "integer"}, /* S4 accepts integers */ "5" : {"D" : 6, "." : 8}, "6" : {"." : 7, "D" : 6}, "7" : {"D" : 7, "ACCEPT" : "real"}, /* S7 accepts real numbers */ "8" : {"D" : 7} }