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
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.
Lecture01_SyllabusDFAsClosurePropertiesofRegularLangs
Lecture02_NFAsandRegularExpressions
Lecture04_PDAsandCFLPumpingLemma
Lecture05_AlanTuringandTuringMachines (python code accompanies this lecture: alphabeticenumerator.py and lexographicenumerator.py)
Lecture06_TMVariantsandEnumeratorsandHilbert
Lecture07_DecidabilityandDiagonalizationandCardinality
Lecture08_ATMUndecidableandHaltingProbandReductions
Lecture09_ReductionsFromATMandPvNP
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 3 – Slides 3-5 have additional questions, please refer to Lecture02_NFAsandRegularExpressions otherwise
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 5 – Slides 11-12 have additional Pumping Lemma introductory material, please refer to Lecture03_PumpingLemmaandCFGs otherwise
Lecture 6 – Slides 2-4 have additional preliminary exam questions, slides 6-14 have additional material on CFGs, please refer to Lecture03_PumpingLemmaandCFGs otherwise
Lecture 7 – Slides 13-17 have additional material, refer to Lecture04_PDAsandCFLPumpingLemma otherwise
Lecture 8 – Slides 2-5 and 18-22 have additional material, refer to Lecture04_PDAsandCFLPumpingLemma otherwise
Lecture 9 – Slide 8 has an additional question, slides 12-23 have additional material, refer to both Lecture05_AlanTuringandTuringMachines and Lecture06_TMVariantsandEnumeratorsandHilbert otherwise
Lecture 10 – Slides 18-22 have additional material, refer to Lecture06_TMVariantsandEnumeratorsandHilbert otherwise
Lecture 11, Lecture 12 – All supplementary material
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 17 – Slides 2-8 and slides 20-27 have additional material, please refer to Lecture09_ReductionsFromATMandPvNP otherwise
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.
– Clickers Week 4
– Clickers Week 5
– Lecture Notes Week 7
– Clickers Week 7