Reversing all the edges of one of these objects is the first step of Brzozowski's algorithm.
Reversing all the edges of one of these objects is the first step of Brzozowski's algorithm. Another algorithm uses partition refinement to merge the nondistinguishable states of one of these objects; that algorithm to minimize these constructs is called Hopcroft's algorithm. The Rabin-Scott powerset construction creates an exponentially large one of these objects. The Myhill-Nerode theorem asserts the existence of one of these objects with as many states are there are equivalence classes among strings in a given (*) regular language. They have precisely once exiting transition arrow for every symbol in their alphabet. Every NFA with n states can be converted to one of these objects with 2^n states. They're not Turing machines, but they consist of an alphabet, a transition function, and a set of states, some of which are called accept states. For 10 points, name this type of finite state machine that non-probabilistically accepts or rejects a given input string.
Reversing all the edges of one of these objects is the first step of Brzozowski's algorithm.
deterministic finite automaton [or DFA; or deterministic finite state machine before giveaway; prompt on partial answer; prompt on finite state machine]