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.

  • …
  • 4/14/2025: We handed back the exams. To earn redo points on the exams you need to redo all the “Exercise” problems on which you got 6 or fewer points. Then we looked at languages that are decidable, recognizable, and non-recognizable.
  • 4/7/2025 – Exam 1 in Chapters 1, 2, & 3.
  • 3/31/2025 – We worked through material in chapter 4 on Turing Machines and started working through the Exploring the Infinite packet. Remember, as it says on the syllabus, the exam on chapters 1, 2, & 3 is next week.
  • 3/24/2025 – We did not have an exam quiz on the 24th since it is the day after break. We briefly review where we left off and then moved on to discuss the material on Turing Machines in Chapter 3, Turing Machines updated (3/24/2025). This concludes all the material that will be on the exam on April 7th. Next week the quiz will pull material from Section 2.3 and Chapter 3.
  • 3/10/2025 – We finished off chapter 2
  • 3/3/2025 – At this point we have covered the material in sections 2.1 and 2.2. We will cover address sections 2.3 and 2.4 next class and perhaps get a start on 3.1.
  • 2/24/2025 – We started discussing Context Free Grammars, the first section in the Grammars and Pushdown Automata (Updated 3/32025) slides. For next week’s quiz be sure your review sections 1.4 and 2.1 upto but not including Chomsky Normal Form. In particular be familiar with
    • The Pumping Lemma for Regular Languages, and how to use it to show that a language is not regular.
    • The Definition of a Context Free Grammar.
    • How to read a grammar and create a parse tree for an expression.
  • 2/10/2025 – Tonight we finished off the material in chapter 1; you should finish reading the chapter as well as studying your notes. When we meet again in two weeks we will start chapter 2.
  • 2/3/2025 – Tonight we had our first quiz and went over the Introduction to Finite Automata (2/4/2025) slides. Be sure to look over the slides and sections 1.1 and 1.2 in the textbook.
  • 1/27/2025 – Tonight we covered the review slides which touch on basic material from chapter 0 sections 2-4. Look over those sections of the text and your notes ahead of next weeks quiz.

Extra Credit

  • Extra Credit: Turing Machine Class Due before 5/12/2025 by 5:30pm
  • Extra Credit: Exploring the Infinite Due before 5/12/2025 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/7/2025

  • 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, & 6) on 5/12/25

  • 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, Oracles, Turing Decidable, Turing Reduction, 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,
    • Organize the different categories of languages,
    • Find/Follow the computational history of a Turing Machine

Lecture Slides (2023 Versions)

Links and Handouts: