Determinisatie

Determinisatie, or determinization, is a standard procedure in automata theory for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) that recognizes the same language. DFAs have exactly one transition for each symbol in every state, which simplifies implementation in tasks such as lexical analysis, parsing, and model checking.

The most common method is the subset construction (powerset construction). In this approach, the states of the resulting DFA correspond to subsets of the NFA’s states. The initial DFA state is the epsilon-closure of the NFA’s start state(s). For each DFA state S and input symbol a, the transition goes to the epsilon-closure of move(S, a), where move(S, a) is the set of NFA states reachable from any state in S by a. A DFA state is accepting if it contains at least one accepting NFA state. If the NFA uses epsilon-transitions, those transitions are handled via epsilon-closures during the construction.

Determinization can lead to an exponential increase in the number of states; the DFA may have up to 2^n states if the NFA has n states. After determinization, minimization can often reduce the number of states further, yielding a smaller equivalent DFA.

Limitations and scope: determinization applies to finite automata recognizing regular languages. It does not generalize to more powerful models such as nondeterministic pushdown automata, which cannot always be determinized.