**Topics Coverage Summary:** Deterministic Finite Auotmata (DFA), Nondeterministic Finite Auomata (NFA), Regular Expressions, Pushdown Auomata (PDA), Context-Free Grammars, Turing Machines, Decidability, Halting Problem, Undecidability, Diagonalization, Reductions, P vs NP.

**Number of Questions/Slides Available: **

– Regular languages: 25 questions

– Context-free languages: 21 questions

– Turing machines: 10 questions

– Decidability, undecidability, cardinality, halting problem, diagonalization: 34 questions

– Reductions, polynomial-time reductions, P vs NP: 14 questions

**Materials Author:** Cynthia Lee, Stanford University

**Additional Contributors:**

– Alex Tsiatas, UCSD

– Thérèse Smith, UConn

Continue reading Theory of Computation Peer Instruction Materials →