Rabin–Scott powerset construction
E836300
The Rabin–Scott powerset construction is a fundamental algorithm in automata theory that converts nondeterministic finite automata (NFAs) into equivalent deterministic finite automata (DFAs) by using sets of states as single states.
Statements (45)
| Predicate | Object |
|---|---|
| instanceOf |
algorithm
ⓘ
automata theory concept ⓘ |
| alsoKnownAs |
powerset construction
NERFINISHED
ⓘ
subset construction NERFINISHED ⓘ |
| appliesTo |
finite automata
ⓘ
regular languages ⓘ |
| assumes | finite set of NFA states ⓘ |
| basedOn | sets of NFA states ⓘ |
| category | determinization algorithm ⓘ |
| defines | each DFA state as a set of NFA states ⓘ |
| ensures | resulting DFA recognizes same language as NFA ⓘ |
| field |
automata theory
ⓘ
theoretical computer science ⓘ |
| formalizes | equivalence of NFA and DFA models of computation ⓘ |
| guarantees | every NFA has an equivalent DFA ⓘ |
| historicalContext | introduced in work of Rabin and Scott on finite automata ⓘ |
| implies | regular languages are closed under determinization ⓘ |
| input | nondeterministic finite automaton ⓘ |
| mathematicalBasis | powerset operation on sets ⓘ |
| namedAfter |
Dana Scott
NERFINISHED
ⓘ
Michael O. Rabin NERFINISHED ⓘ |
| output | deterministic finite automaton ⓘ |
| outputProperty |
resulting DFA has no epsilon-transitions
ⓘ
resulting DFA is deterministic ⓘ |
| preserves | recognized language ⓘ |
| property |
can cause exponential blowup in number of states
ⓘ
produces DFA equivalent to original NFA ⓘ |
| purpose | convert nondeterministic finite automata to deterministic finite automata ⓘ |
| relatedTo |
determinization
ⓘ
epsilon-closure ⓘ state explosion problem ⓘ |
| requires | complete specification of NFA transitions ⓘ |
| step |
DFA accepting states are subsets containing at least one NFA accepting state
ⓘ
DFA transition on symbol is union of NFA transitions from all states in subset ⓘ initial DFA state is epsilon-closure of NFA start state ⓘ |
| typicalStateBlowup | up to 2^n states from n-state NFA GENERATED ⓘ |
| usedFor |
decision procedures for regular languages
ⓘ
proving equivalence of NFAs and DFAs ⓘ regular expression to DFA conversion pipelines ⓘ |
| usedIn |
compiler design
ⓘ
formal verification ⓘ lexical analysis ⓘ model checking ⓘ |
| uses | powerset of the NFA state set ⓘ |
| worstCaseComplexity | exponential in number of NFA states ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject surface form:
Michael O. Rabin