**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