Class 19: Computability

Here’s the notes handed out today: tmnotes.pdf (Warning: do not print in color unless you are familiar with UK counterfeiting laws!)

Slides from class: class19.pdf

There is a Quiz due Wednesday at 9:59pm, posted in Gradescope.

Problem Set 8 is due on Monday, 10 April. The latex template is https://www.overleaf.com/read/nhgcvwvnfvkh.

Class 18: Turing Machines

Slides from class: class18.pdf Here are the links to the Turing Machine simulations: 4-state Busy Beaver candidate 5-state Busy Beaver candidate As mentioned in class, there are lots of different ways to define a Turing Machine, and no agreed upon standard definition. None of the small changes to the definition impact the set of functions that can be computed (as we will see in upcoming classes), but they do impact how hard it might be to write programs and prove properties about Turing Machines.

Read More…

Class 17: NFA vs. RE

Slides from class: class17.pdf

There is a Quiz due Wednesday at 9:59pm, posted in Gradescope.

Problem Set 7 is due on Monday, 27 March. The latex template is https://www.overleaf.com/read/krxvcbgfpkgk.

Class 16: Completing DFA=RE Proof

Slides from class: class16.pdf

Problem Set 6 is due on Monday, 27 March. The latex template is https://www.overleaf.com/read/bfftypdhtryf.

Python’s Regular Expression library code is here: https://github.com/python/cpython/blob/3.11/Lib/re/_parser.py (see lines starting at 634 for the implementation of repetition patterns including the (bogus?) Kleene star).

Cloudflare Outage, July 2, 2019

Class 15: Deterministic and Nondeterministic FAs

Slides from class: class15.pdf

Notes of Finite Automata (these are the completed version of the notes that were handed out in class today)

Problem Set 6 is due on Monday, 27 March. The latex template is https://www.overleaf.com/read/bfftypdhtryf.

Class 14: Regular Expressions

Slides from class: class14.pdf

Problem Set 5 is posted in grade scope (latex template available here: https://www.overleaf.com/read/jmpfnvfffgrb), and is due 9:59pm, Monday, 20 March.

Class 13: Finite Automata and Regular Expressions

Slides from class: class13.pdf (video is available for students in collab)

Problem Set 5 is posted in grade scope (latex template available here: https://www.overleaf.com/read/jmpfnvfffgrb), and is due 9:59pm, Monday, 20 March.

There is no quiz this week.

If you are unclear on the difference between the Kleene-* (the * used in regular expressions introduced in class today) and Kleene-X, the videos here will almost certainly not help you.

Midterm Comments

The midterm exam and comments on its are now posted:

Class 12: Review

Slides from class (including slides that were not used): class12.pdf (video is available for students in collab)

The Midterm Exam will be in class on Thursday, 2 March.

Class 11: Universal Circuits, Quiz Questions, Practice Problems

Slides from class: class11.pdf (video is available for students in collab)

The Midterm Exam will be in class on Thursday, 2 March. Tuesday’s class with be a review. If there are any topics you would like covered, or particular problems to go over, please let us know in the Discord. See Preparing for Exam 1 for suggestions on how to prepare for the exam.

All Posts by Category or Tags.