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

How to Convert NFAs to DFAs Using This Tool

Suppose you have the following NFA:

You want to represent it as JSON, so this app will do the subset construction algorithm for you and render the resultant DFA.

Input the NFA as JSON

You'd type up an NFA as below. Probably without comments. Note: the below box is a read-only sample. The big one on the left is editable, and is where your input belongs.

/* Comments look like this */
{
  /* State 0 (S0) has ε-edges
     to S1 & S3. */
  "0" : {"" : [1,3]},
  
  /* S1 has a D edge to S2. */
  "1" : {"D" : 2},

  /* S2 accepts integers. */
  "2" : {"D" : 2,
         "ACCEPT" : "integer"},
  "3" : {"D" : 4,
         "." : 6},
  "4" : {"." : 5,
         "D" : 4},
  
  /* S5 accepts reals. */
  "5" : {"D" : 5,
         "ACCEPT" : "real"},
  "6" : {"D" : 5}
}

Input is whitespace insensitive. Well, except in strings. (Duh.)

Once you're done, slam the big button and receive a cookie your DFA will appear in this sidebar. Also, a ruby module will appear below the input field. Said module can be used with a parser driver.