Subset construction (powerset construction)
GPTKB entity
Statements (18)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:algorithm
|
| gptkbp:alsoKnownAs |
powerset construction
|
| gptkbp:complexity |
exponential in number of NFA states
|
| gptkbp:describedBy |
Hopcroft and Ullman, Introduction to Automata Theory, Languages, and Computation
|
| gptkbp:field |
theoretical computer science
|
| https://www.w3.org/2000/01/rdf-schema#label |
Subset construction (powerset construction)
|
| gptkbp:input |
gptkb:nondeterministic_finite_automaton
|
| gptkbp:output |
gptkb:deterministic_finite_automaton
|
| gptkbp:relatedTo |
gptkb:finite_automata
regular languages |
| gptkbp:step |
construct states as subsets of NFA states
define transitions based on NFA transitions identify start state as subset containing NFA start state identify accepting states as subsets containing NFA accepting states |
| gptkbp:usedFor |
converting NFA to DFA
|
| gptkbp:usedIn |
automata theory
|
| gptkbp:bfsParent |
gptkb:Nondeterministic_finite_automaton
|
| gptkbp:bfsLayer |
7
|