NFA to DFA conversion (NFA to DFA conversion)

From Algorithm Wiki
Jump to navigation Jump to search


Convert a given nondeterministic finite automota (NFA) to a deterministic finite automota (DFA).


$n$: number of states in the given NFA

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Rabin–Scott powerset construction 1959 $O({2}^n)$ $O({1})$ Exact Deterministic Time

Time Complexity Graph

NFA to DFA conversion - Time.png