Determinization of Automaton

In theoretical computer science and automata theory, determinizing a non-deterministic automaton is a very important procedure. This procedure accepts a non-deterministic automaton of some type and returns another deterministic automaton that recognizes the exact same formal language.

Such procedure for some type of automata are very useful for their software implementation. For example, if one have a query to check for a given word if it is accepted by a given non-deterministic automaton then one have to check every possible run of the automaton. Alternatively, one can determinize the given non-deterministic automaton and then, for each instant of above query, one will have to check only one run.

For example, the powerset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA).