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

Day	“Monday” Cohort	“Tuesday” Cohort	“Wednesday” Cohort	“Thursday” Cohort	“Friday” Cohort
Wed 29 Sept	Preparation	(Week 5)	(Week 5)	(Week 5)	(Week 5)
Thurs 30 Sept	Preparation	Preparation	(Week 5)	(Week 5)	(Week 5)
Fri 01 Oct	Preparation	Preparation	Preparation	(Week 5)	(Week 5)
Sat 02 Oct	Prep Cohort Meeting	Preparation	Preparation	Preparation	(Week 5)
Sun 03 Oct	Revision	Prep Cohort Meeting	Preparation	Preparation	Preparation
Mon 04 Oct	Assessed Meeting	Revision	Prep Cohort Meeting	Preparation	Preparation
Tues 05 Oct	Writeup Due	Assessed Meeting	Revision	Prep Cohort Meeting	Preparation
Wed 06 Oct	(Week 7)	Writeup Due	Assessed Meeting	Revision	Prep Cohort Meeting
Thurs 07 Oct	(Week 7)	(Week 7)	Writeup Due	Assessed Meeting	Revision
Fri 08 Oct	(Week 7)	(Week 7)	(Week 7)	Writeup Due	Assessed Meeting
Sat 09 Oct	(Week 7)	(Week 7)	(Week 7)	(Week 7)	Writeup 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:

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.

There is no programming problem this week.

As with Week 5, you will be given a new problem for the write-up this week, and need to solve it individually. The assigned write-up problem will be similar to Problem 1 and Problem 4 from this assignment.

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

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