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-30-2023 – …
  • 1-23-2023 – We began by going over the syllabus, discussed how the class would run and the expectations for this class. We spent the rest of class working through the review slides (Review Material). Be sure to study the slides, and chapter 0 of your text if you have it, for the quiz at the start of class next week.

Assignments:

All out of class work in this class must be typed up (double spaces, 1in margins, 12pt font) and in complete sentences.

  • Chapter 1: p.83 – 1.3, 1.4c, 1.5c, 1.6ej, 1.12, 1.18ej, 1.21b, 1.22, 1.28a, 1.29b Due 2/13/2023
  • Chapter 2: p. 154: 2.1, 2.2, 2.4bc, 2.5bc, 2.11, 2.13, 2.14, 2.15, 2.16 Due 3/20/2023
  • Chapter 3: p.187: 3.1cd, 3.2cd, 3.8b, 3.9, 3.15bc, 3.16bc Due 4/3/2023
  • Chapter 4: p.210: 4.3, 4.4, 4.6 4.7 4.11, 4.13 Due 4/17/2023
  • Chapter 5: Chapter 5: p.239 – 5.1 (use Theorem 5.13 and show that \(ALL_{CFG}\leq_m EQ_{CFG}\)), 5.2 (Show, directly, that  \(\overline{EQ}_{CFG}\) is recognizable), ?? Due 5/1/2023
  • Chapter 6: p.270 – 6.1, 6.11 (look at 6.10), 6.28 (look at 6.12), ??, Due 5/12/2023 by 5pm
  • Extra Credit: Turing Machine Class Due 5/12/2023 by 5pm
  • Extra Credit: Exploring the Infinite Due 5/12/2023 by 5pm

Exam Guides:

Unit 1: Automata and Languages Exam (Chapters 1& 2)

  • Definitions:
  • ??

Unit 2: Computability Theory Exam 1 (Chapters 3 & 4)

  • Definitions:
  • ??

Unit 3: Computability Theory Exam 2 (Chapters 5 & 6)

  • Definitions:
  • ??

Lecture Slides (2022 Versions)


Links and Handouts: