Theory of Computation

Syllabus

Calendar:

The calendar on the syllabus is the plan for this semester, this calendar reflects in detail what we actually get to cover in class and when.

  • …
  • 3/30/2026: We covered the first set of slides on Turing Machines, looked at equivalent machines, and defined Turing-Decidable and Turing-Recognizable. Next week is the Exam on Unit 1 covering chapters 0, 1, and 2, see the study guide below.
  • 3/23/2026: We reviewed material on context free grammars and pushdown automata. We reviewed regular grammars and the pumping lemma for regular languages. Then looked at the pumping lemma for context free languages. This finishes off chapter 2. The exam Next Next Week on April 6th will be on chapters 0, 1, and 2. Chapter 3 is moved to the next unit. Review chapter 2 for the quiz on 3/30/2026.
  • 3/9/2026: We reviewed grammars by looking at ascii math. Then we went over Chomsky Normal Form and Push-Down Automata. We finished by showing how to convert a grammar to a PDA. We will pick up next class showing how to convert PDA to a grammar.
  • 3/2/2026: We reviewed NFAs, GNFAs, and Regular Expressions. We then looked at the Pumping Lemma for Regular Expressions and used it to show that certain languages are not regular (specifically those that require us to count and remember). We ended by introducing Context Free Grammars. We will pick up there next week.
  • 2/23/2026: picture of a snowing cloud Snow Day picture of a snowing cloud The calendar will shift as needed. I will consider splitting the unit 1 exam into two or shifting the content of the exams to account for the missed days. I will let you know the details next week. You should be sure to study the material we have covered so far in preparation for next weeks quiz.
  • 2/9/2026: Note that the Lecture 1 Slides were updated with an additional example of constructing a union. We finished the slides on DFAs and NFAs and started the slides on Reg. Exp.. We finished the first couple sections on those and will pick up next week with the Pumping Lemma.
  • 2/2/2026: Today we went over the syllabus, the set of review slides, and the first two sections of the slides on Introduction to Finite Automata. Take a look at that material for next weeks quiz.
  • 1/26/2026: picture of a snowing cloud Snow Day picture of a snowing cloud: I will adjust the calendar and we will get started next week.

Extra Credit

  • Extra Credit: Turing Machine Class(Needs Revision!!!) Due before 5/12/2026 by 5:30pm
  • Extra Credit: Exploring the Infinite Due before 5/12/2026 by 5:30pm (We’re doing most of this in class, so for the extra credit you need to answer all the questions typed up neatly.)

Exam Guides:

Unit 1: Automata and Languages Exam (Chapters 1, 2, & 3) on 4/6/2026

  • Definitions: Deterministic and Non-Deterministic Finite State Automata, Regular Languages, Unions, Concatenation, Star Operation, Generalized Non-Deterministic Finite State Automata, Regular Expressions, Pumping Lemmas, Context Free Grammars, Parse Tree, Chomsky Normal Form, Pushdown Automata, …
  • Be Able To:
    • Create basic NFAs or DFAs to recognize simple languages
    • State explicitly \(A\cup B\), \(A\circ B\), \(A^*\), and \(A^+\) for small sets \(A\) and \(B\)
    • Simplify a GNFA to create a regular expression
    • Apply to Pumping Lemma for regular languages to show a language is not regular
    • Identify Context Free Grammar and make “simplifications” to it to change it to Chomsky Normal Form
    • Write a parse tree for an expression based on a grammar
    • Read and explain the action of a Pushdown Automata
    • Apply the pumping lemma to show a language is not context free.
  • Challenge Questions: Three of the following will be on the exam and each count for 7% of the exam grade.
    • Chapter 0: 0.7, 0.11, 0.14
    • Chapter 1: 1.12, subset of 1.24-1.27, 1.40
    • Chapter 2: 2.2, 2.18, 2.20, 2.26
  • Slides:
    1. Review Material (2025 Version)
    2. Introduction to Finite Automata (2/9/2026)
    3. Reg. Exp. and the Pumping Lemma (Updated)
    4. Grammars and Pushdown Automata (Updated 3/3/2025)
    5. Grammars and Pumping Lemmas

Unit 2: Computability Theory Exam (Chapters 4, 5, & 7) on ???

  • Definitions: Decidable Language, Recognizable Language, Regular Language, Context Free Language, Cardinality of a Set, Power Set, Turing Recognizable and co-Recognizable, Reducible, Computable Function, Mapping Reducible, Computational History, linear bounded automaton, Turing Machine, Formal, Implementation, and High-Level Descriptions, Multitape Turing Machine, Enumerator, Algorithm, …
  • Be Able To:
    • Organize the different categories of languages
    • Describe the diagonalization process
    • Explain why two sets are the same cardinality
    • Describe the power set of a set
    • Demonstrate understanding of predicates, quantifiers, and what it means for a statement to be true,
    • Read a diagram of a Turing Machine,
    • Follow a High-Level Description of a Turing Machine,
    • Find/Follow the computational history of a Turing Machine

Lecture Slides (2023 Versions)

Links and Handouts: