uconn codeNFA to DFA
NFA → DFA converter
CSE 237 · 2001 · C++, rebuilt in TypeScript in 2026
In automata theory, a nondeterministic finite automaton (NFA) can be in several states at once and can move on ε (taking no input at all). Every NFA has an equivalent deterministic automaton (DFA) that is in exactly one state at a time. For CSE 237 in fall 2001 I wrote a C++ console program that does the conversion in two steps: first remove the ε-moves, then build the DFA by subset construction.
My write-up was honest about it: “This program is extremely ugly and un-user-friendly, but it does work.” This version runs the same two steps in your browser, accepts the same input format, and still prints its results the way the 2001 program did.
Try it
1. ε-closures
Every state reachable from each state using ε-moves alone.
| State | ε-closure |
|---|
2. NFA without ε-moves
δ′(q, a) = ε-closure(δ(ε-closure(q), a)). A state is final if its ε-closure contains a final state.
3. DFA (subset construction)
Each DFA state is a set of NFA states, starting from {0}. ∅ is the trap state, which the 2001 program called −1.
As the 2001 program printed it
In the original console format, -> marks the start state and F marks a final state. Combined states are named by joining their states with 0s.
NFA
DFA
What changed since 2001
- Combined state names. The original named a combined state by joining its states with 0s and stored the name as an integer, so {0, 1, 2} printed as 102 instead of 00102. The write-up apologized: “I'm sorry for this design flaw. To fix it, I would have had to overhaul the code.” Names are real sets now, and the 2001-style printout keeps the leading zero.
- Final states. A state whose ε-closure reaches a final state is now final too, as the textbook construction requires.
- Reachable states only. The DFA is built outward from {0}, so states you can never reach are left out, and sets of any size work.
- No more “Press Enter to continue”. The original paused every three states so the output wouldn't scroll off the DOS window.
The 2001 source
3 files, 720 lines, exactly as written apart from line endings.
drivernfa.cpp · 57 lines
//Stephen Bassoli
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include "FAmanip.h"
extern char alphabet[10];
int main()
{
int states, alpha, from, to;
char via;
char useless[2];
cout << "How many states will there be? ";
cin >> states;
cout << "How big will the alphabet be without (E)psilon? ";
cin >> alpha;
FAmanip FA(states,alpha);
cout << "Begin entering connections in the format: from via to\n";
cout << "For example 1 E 2 says state 1 goes to state 2 on epsilon\n";
cout << "The states start at 0 and ascend, the alphabet begins at 'a' and ascends\n";
cout << "Enter connections now (end by typing '-1'):\n\n";
while (true)
{
cin >> from;
if (from == -1)
{
cin.ignore(255,'\n');
break;
}
cin >> via >> to;
FA.setConnection(from,to,via);
}
cout << "What states will be final states? End with -1\n";
while (true)
{
cin >> from;
if (from == -1)
{
cin.ignore(255,'\n');
break;
}
FA.setEndState(from);
}
cout << "Press enter to convert into an NFA\n";
cin.getline(useless,2,'\n');
FA.CONVERTtoNFA();
FA.printFA();
cout << "Press enter to convert into a DFA\n";
cin.getline(useless,2,'\n');
FA.CONVERTtoDFA();
FA.printFA();
cout << "Press enter to quit\n";
cin.getline(useless,2,'\n');
return 0;
}