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.

  • 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


Exam Guides:

  • 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
    5. Grammars and Pumping Lemmas
    6. Turing Machines

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: