Theory of Computation

Syllabus

Spring 2026 Final Exam Week Schedule

All work is due by 3pm on Friday May 15th. Office hours and times for exams and presentations are below.

Exams and Such:

  • Monday 5/11/26: MAT 375: Algebraic Structures Last Exam 11-1:30
  • Monday 5/11/26: MAT 429/529: History of Math Last Exam 2-4:30
  • Monday 5/11/26: MAT 359: Theory of Computation Last Exam 5:30-8
  • Tuesday 5/12/26: MAT 141: Foundational Discrete Mathematics Last Exam 2-4:30
  • Wednesday 5/13/26: HON 398-02: Rolling for Knowledge Presentations 5:30-8

Office Hours:

  • Tuesday 12:45-1:45
  • Wednesday 4:30-5:30
  • Friday: 1-3

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.

  • …
  • 5/8/2026: The Unit 2 study guide below has been updated. And for the Turing Machine Extra credit remember that for the multiplication portion
    1. you only need to multiply two positive integers
    2. your multiplication function is allowed to copy its own tape like a multitape machine and refer to both tapes, (one possible implementation of this is listed below with the extra credit) and
    3. your multiplying machine can also create an instance of other machines and use them, so it could for create an instance of ADD use it to get a sum to record to its own tape.
  • 4/27/2026: We discussed material from the start of chapter 7, specifically we looked at the definition of big O and little o notation, the definition of time complexity, and the collection of polynomial time algorithms, P. Next time we see why CFG are all polynomial time and discuss the definition of NP. We will also spend time reviewing provided that you bring questions.
  • 4/20/2026: We went over the second set of slides on limits of Turing Machines. We will look at some chapter 7 material next week.
  • 4/13/2026: We went through the slides on Limits of Turing Machines (Updated 4/13/2026). Be sure to review the slides and your notes ahead of the quiz next week. You should get the redos on your exam to me by 4/27/2026.
  • 4/6/2026: Exam on Chapters 0-2. Next week we will have a quiz on the material we covered on Turing Machines on 3/30/2026.
  • 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.)
# To use this implementation your Turing Machine tapes
# must end in EOT which is moved along when inserting 
# new elements on the right hand end of the tape.
def copy_tape(M):
        new_tape = TM()
        while M.head()!="EOT":
                new_tape.write(M.head())
                M.move_right(M.state)
                new_tape.move_right("q0")
        while new_tape.position!=0:
                M.move_left(M.state)
                new_tape.move_left("q0")
        return new_tape

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 5/11/2026

  • 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: