Determinization of finite state machine
For every finite state machine there exists a deterministic finite state machine that accepts the same language.
This machine is given by where
- .
The corresponding deterministic state machine maintains a set of states instead of just one state, and simultaneously transitions into all states that the original machine could reach from the current set of states.