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:
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:
- Review Material (2025 Version)
- Introduction to Finite Automata (2/3/2025)
- Reg. Exp. and the Pumping Lemma (Updated)
- Grammars and Pushdown Automata
- Grammars and Pumping Lemmas
- 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: