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
Sample Peer Instruction Questions (click to enlarge):
Slides for Intro. to Theory of Computation Course Lectures by Dr. Cynthia Lee, UCSD is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Based on a work at www.peerinstruction4cs.org.
Permissions beyond the scope of this license may be available at http://www.peerinstruction4cs.org/2012/03/19/theory-of-computation-peer-instruction-materials/.
These materials are divided into 3-hour long lectures. We take a 10-minute break in the middle, so most of these break fairly naturally into 1.5-hour lectures (and I’ve taught it in 1.5-hour format using these materials and it worked well). I can’t speak to the 1-hour lecture scenario.
These are additional materials:
–Instructor’s guide to understanding the pedagogical strategy behind the DFA introduction slides: Introducing DFA Formal Description Using Peer Instruction
–Student study guide for Pumping Lemma (packages up the lecture slides in that segment): The Pumping Lemma
–Student study guide for Reductions from A_TM (packages up lecture slides and adds extensive additional commentary): ReductionFromATM_StudentSelf-StudyTutorial
Additional slides by Alexander Tsiatas:
Lecture 1, Lecture 2 – Please refer to Lecture01_SyllabusDFAsClosurePropertiesofRegularLangs
Lecture 4 – Slide 8 is a slightly different version of the same question in Lecture02_NFAsandRegularExpressions, Slide 9 provides additional examples of regular expressions, Slides 12-21 have additional questions and material, please refer to Lecture02_NFAsandRegularExpressions otherwise
Lecture 13 – Please refer to Lecture07_DecidabilityandDiagonalizationandCardinality
Lecture 14 – Slides 22-23 have addtional questions, please refer to both Lecture07_DecidabilityandDiagonalizationandCardinality and Lecture08_ATMUndecidableandHaltingProbandReductions otherwise
Lecture 15 – Slide 13 and slides 19-25 have additional material, please refer to Lecture08_ATMUndecidableandHaltingProbandReductions otherwise
Lecture 16 – All supplementary material
Lecture 18 – All supplementary material
New PI questions in these slides are offered under a Creative Commons license as follows:
Theory of Computation Lecture Materials by Thérèse Smith is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Based on a work at http://peerinstruction4cs.org.
Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org.