Simple examples of these things can have their structure defined by transition diagrams or transition tables.
The best known algorithm for minimizing these things uses partition refinement and is named for John Hopcroft. Two types of these things, which are differentiated on the basis of whether an output is a function of the input, are named for Mealy and Moore. Lexical analyzer generators work by converting a regular expression into one of these things. Using the powerset construction, one can convert them from a nondeterministic form to a deterministic form. Simple examples of these things can have their structure defined by transition diagrams or transition tables. The set of strings that allow these things to progress from a starting state to the accepting state is the language they accept. For 10 points, name these computational models without an infinite number of states.
The best known algorithm for minimizing these things uses partition refinement and is named for John Hopcroft.
finite state machines [or finite state automata; or FSM; or FSA; or deterministic finite automata; or DFA; or nondeterministic finite automata; or NFA]