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.

  • …
  • 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 ???

  • Definitions: Deterministic and Non-Deterministic Finite State Automata, Regular Languages, Unions, Concatenation, Star Operation, Generalized Non-Deterministic Finite State Automata, Regular Expressions, Pumping Lemma, Context Free Grammars, Parse Tree, Chomsky Normal Form, Pushdown Automata, Turing Machine, Formal, Implementation, and High-Level Descriptions, Multitape Turing Machine, Enumerator, Algorithm, …
  • 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
  • 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
    • Chapter 3: 3.7, 3.9, 3.10
  • Slides:
    1. Review Material (2025 Version)
    2. Introduction to Finite Automata (2/3/2025)
    3. Reg. Exp. and the Pumping Lemma (Updated)
    4. Grammars and Pushdown Automata (Updated 3/3/2025)
    5. Grammars and Pumping Lemmas
    6. Turing Machines updated (3/24/2025)

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, Self Replicating, Recursion, Universal Quantifier, Existential Quantifier, Model, Theory, Provability, Information, Minimal Description, Descriptive Complexity, Compressible.
  • 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
  • Challenge Questions: Three of the following will be on the exam and each count for 7% of the exam grade. I will put four questions on the exam, two from unit 1 and two from unit 2; you will need to do at least three of the four and may do the other for extra credit.
    • Chapter 1: 1.12, subset of 1.24-1.27, 1.40
    • Chapter 2: 2.2, 2.18, 2.20, 2.26
    • Chapter 3: 3.7, 3.9, 3.10
    • Chapter 4: 4.4,4.7,4.9
    • Chapter 5: 5.4, 5.7
    • Chapter 7: ????
  • Slides:
    1. Limits of Turing Machines
    2. Limits of Turing Machines (part 2)
    3. ??? Recursion and Decidability ???
    4. ??? Reducibility and Information ???

Lecture Slides (2023 Versions)

Links and Handouts: