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/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: Snow Day : I will adjust the calendar and we will get started next week.

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.)

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:

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