Bonus

Hopcroft’s algorithm can be used to minimize one type of these constructs. For 10 points each:
[10h] Name these models of computation which are equivalent to regular languages by Kleene’s theorem. The subset construction algorithm converts the “nondeterministic” type of these constructs into a “deterministic” type.
ANSWER: finite automata [or finite automaton or FAs; or finite state machines or FSMs; or finite state automata or FSAs; accept nondeterministic finite automata or NFAs; accept deterministic finite automata or DFAs; accept nondeterministic finite state machines or NFSMs; accept deterministic finite state machines or DFSMs; accept nondeterministic finite state automata or NFSAs; accept deterministic finite state automata or DFSAs; prompt on automata or automaton or state machines or state automata]
[10m] Push-down automata consist of a finite automaton and one of these data structures, allowing them to accept context-free languages. Operations on these last-in, first-out data structures include push and pop.
ANSWER: stacks
[10e] Recursively-enumerable languages can be accepted by machines named after this computer scientist, who theorized a test in which a machine imitates human behavior.
ANSWER: Alan Turing [or Alan Mathison Turing; accept Turing machines; accept Turing test]
<Editors, Other Science>

EditionsHeardPPBEasy %Medium %Hard %
2916.67100%56%11%

Back to bonuses

Conversion

TeamOpponentPart 1Part 2Part 3TotalParts
Boston College AVermont B001010E
Brown ADartmouth B0101020ME
Brown BAmherst A001010E
Maryland AGeorge Mason A0101020ME
McMaster AToronto B001010E
Rutgers AMaryland C0101020ME
UC Santa BarbaraClaremont A10101030HME
Vanderbilt AChipola College0101020ME
Williams BDartmouth A001010E

Summary

TournamentEditionExact Match?HeardPPBEasy %Medium %Hard %
Southern CaliforniaUSY130.00100%100%100%
Eastern Canada (2)USY110.00100%0%0%
Upper Mid-AtlanticUSY220.00100%100%0%
NortheastUSY412.50100%25%0%
SoutheastUSY120.00100%100%0%