NFA-to-DFA Converter
A finite-automata project that converts an NFA defined by transitions and accepting states into an equivalent DFA through reachable state subsets.
This project addresses the conversion of a nondeterministic finite automaton (NFA), defined by its transition table and accepting states, into a deterministic finite automaton (DFA) that recognizes the same language.
State Subsets
A single DFA state can represent a set of NFA states that may be reachable after the same input prefix. The conversion therefore constructs reachable subsets rather than copying NFA states one by one.
Starting from the initial set, the algorithm computes the NFA states reachable for each input symbol. A subset that has not been seen before becomes a new DFA state and is processed in the same way. Construction ends when no new reachable subsets remain.
A DFA state is accepting when its represented subset contains at least one accepting NFA state.
Making the Transition Deterministic
An NFA can have multiple possible destinations for one state/symbol pair. A DFA requires exactly one destination per state/symbol pair. Subset construction encodes those alternatives into one deterministic transition table.
If an NFA model includes epsilon transitions, epsilon-closure must also be considered. The surviving project record does not document every accepted input form, so the description is limited to the subset construction and transition behavior established by the project.
Theory
The broader formal-language context is covered in my Automata Theory and Formal Languages notes. The useful part of this project is the translation of a formal equivalence result into an executable state-table transformation.
