Question
A generalization of these objects simulates parallelism by dividing transitions into “existential” and “universal” types. For 10 points each:
[10h] Name these objects that can be converted to a simpler equivalent type by applying a powerset construction. Unlike that simpler type, these objects may possess epsilon transitions corresponding to reading an empty string.
ANSWER: nondeterministic finite automaton [or NFA or nondeterministic finite-state machine or NFSM; prompt on finite automaton or finite-state machine; reject “deterministic finite automaton” or “DFA” or “deterministic finite-state machine” or “DFSM”]
[10m] Kleene’s (“KLEE-nee’s”) theorem states that formal languages are described by this term if and only if they can be accepted by an NFA. String sequences described by this term are processed by the Unix tool grep.
ANSWER: regular [accept regular languages or regular expressions; accept regex; accept rational languages or rational expressions]
[10e] Equivalently, regular languages can be defined as those accepted by a “read-only” type of this British scientist’s namesake machines, which simulate instructions on an infinitely long tape.
ANSWER: Alan Turing [accept (read-only) Turing machines]
<Other Science>