This is an archived page from the Fall 2019 version of the course.
For the latest version, see https://uvatoc.github.io.

Week 6

Goals

The main goals for Week 6 are to:

  • Synthesize what we have learned about finite computation in the first 5 weeks, and start exploring unbounded computation.

  • Appreciate the connection between functions and languages, and the different ways of talking about computation.

  • Understand and be able to formally define a Finite State Automaton, and to reason about the language accepted (or function computed) by a Deterministic Finite Automaton.

  • Be able to reason about the power of a DFA and understand deeply the proof that DFAs are strictly more powerful than Boolean circuits.

  • Understand how to interpret Regular Expressions, define them formally, and reason about their capabilities.

Schedule

The schedule is identical to previous weeks, and repeated here (with updated dates).

Day "Tuesday" Cohort "Wednesday" Cohort "Thursday" Cohort "Friday" Cohort "Sunday" Cohort "Monday" Cohort
Wed 30 Sep Preparation (Week 5) (Week 5) (Week 5) (Week 5) (Week 5)
Thu 1 Oct Preparation Preparation (Week 5) (Week 5) (Week 5) (Week 5)
Fri 2 Oct Preparation Preparation Preparation (Week 5) (Week 5) (Week 5)
Sat/Sun 3/4 Oct Cohort Meeting Preparation Preparation Preparation (Week 5) (Week 5)
Mon 5 Oct Preparation Cohort Meeting Preparation Preparation Preparation (Week 5)
Tue 6 Oct Assessed Cohort Meeting Preparation Cohort Meeting Preparation Preparation Preparation
Wed 7 Oct Write-up Due Assessed Cohort Meeting Preparation Cohort Meeting Preparation Preparation
Thu 8 Oct Week 7 Write-up Due Assessed Cohort Meeting Preparation Cohort Meeting Preparation
Fri 9 Oct Week 7 Week 7 Write-up Due Assessed Cohort Meeting Preparation Cohort Meeting
Sat/Sun 10/11 Oct Week 7 Week 7 Week 7 Write-up Due Assessed Cohort Meeting Preparation
Mon 12 Oct Week 7 Week 7 Week 7 Week 7 Write-up Due Assessed Cohort Meeting
Tue 13 Oct Week 7 Week 7 Week 7 Week 7 Week 7 Write-up Due

Cohort Problems

These are the problems you should discuss in your Cohort Meeting, and everyone in your cohort should be prepared to present and discuss solutions to at the Assessed Cohort Meeting:

Cohort Problems for Week 6 [PDF]

The problems are posted here and we think its a good idea to look at them early, but you’re not expected to be able to solve them until after doing the readings and watching the videos below.

After the Assessed Cohort Meeting, your Cohort Leader will select one problem that your cohort needs to write-up and submit. The write-up is due by 11:59pm on the day after your assessed cohort meeting (see the schedule above).

Problem Set 6 Template [zip].

Reading

This week focuses on material in Chapter 6: Functions with Infinite domains, Automata, and Regular expressions. Our presentation in the videos differs from how things are presented in the textbook (our way of defining a DFA is closer to the Alternate Definition mentioned in Remark 6.3 than the way Definition 6.2 defines a DFA; the book’s presentation on regular expressions is similar to ours, but not identical). Astute readers and viewers are encouraged to look for places where the differences matter, or if they are only cosmetic.

Videos

You can play all the videos using this playlist, but don’t forget to take breaks: Week 6 Playlist

These videos are edited from these cs3102 classes (we don't generally recommend watching the unedited versions, but they are available if you want to):

Warm-up: Questions about Strings (4:01)

Functions and Languages (11:16)

Breaktime

Beyond Finite Functions (8:23)

Finite Automaton for XOR (6:28)

Formalizing Finite State Automata (3:29)

Breaktime

Power of Deterministic Finite Automata (8:15)

Breaktime

Regular Expressions (17:27)