The main goals for Week 7 are to:
Understand the proof that Regular Expressions are equivalent in power to Deterministic Finite Automata. This is a long proof, split over 4 videos, but is something we hope everyone understands in detail. The methods used in the proof are similar to ones we have seen before in showing equivalence of NAND-Circ and Boolean circuits, but is a fair bit more complex. This general method of showing equivalence is something we will see again in this class, and you will encounter many more times in other classes and work that you will do.
Become familiar with the power and strangeness of nondeterminism. For finite automata, we prove this week that despite is seeming super-power, nondeterministic finite automata cannot compute any functions (or recognize any languages) that cannot be computed by deterministic finite automata. The main topic for Weeks 8-11 will be considering this question for more powerul computing models (which is the most famous open problem in computer science).
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 7 Oct||Preparation||(Week 6)||(Week 6)||(Week 6)||(Week 6)||(Week 6)|
|Thu 8 Oct||Preparation||Preparation||(Week 6)||(Week 6)||(Week 6)||(Week 6)|
|Fri 9 Oct||Preparation||Preparation||Preparation||(Week 6)||(Week 6)||(Week 6)|
|Sat/Sun 10/11 Oct||Cohort Meeting||Preparation||Preparation||Preparation||(Week 6)||(Week 6)|
|Mon 12 Oct||Preparation||Cohort Meeting||Preparation||Preparation||Preparation||(Week 6)|
|Tue 13 Oct||Assessed Cohort Meeting||Preparation||Cohort Meeting||Preparation||Preparation||Preparation|
|Wed 14 Oct||Write-up Due||Assessed Cohort Meeting||Preparation||Cohort Meeting||Preparation||Preparation|
|Thu 15 Oct||Week 8||Write-up Due||Assessed Cohort Meeting||Preparation||Cohort Meeting||Preparation|
|Fri 16 Oct||Week 8||Week 8||Write-up Due||Assessed Cohort Meeting||Preparation||Cohort Meeting|
|Sat/Sun 17/18 Oct||Week 8||Week 8||Week 8||Write-up Due||Assessed Cohort Meeting||Preparation|
|Mon 19 Oct||Week 8||Week 8||Week 8||Week 8||Write-up Due||Assessed Cohort Meeting|
|Tue 20 Oct||Week 8||Week 8||Week 8||Week 8||Week 8||Write-up Due|
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.
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).
This week continues with the material in Chapter 6: Functions with Infinite domains, Automata, and Regular expressions that we started on last week.
Section 6.4.2 of the book includes a proof that regular expressions are equivalent in power to deterministic finite automata, but it is quite different from the proof we do in the videos. Ambitious students are encouraged to understand both proofs, and to consider the advantages and disadvantages of the approach taken in the book compared to our approach (which is the one done more traditionally in theory of computation courses, at least going back to Mike Sipser’s courses in the 1980s).
There are many books (and other videos) that do present material similar to what is in the videos this week, but we are not assigning any additional readings.
You can play all the videos using this playlist, but don’t forget to take breaks: Week 7 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):
- (Spring 2020) Nondeterminism: Full Video, Slides
- (Spring 2020) FSA Equivalent to Regular Expressions: Full Video, Slides
Warm-Up: Complementing the XOR Language (5:54)
Equivalence of Regular Expressions and FSAs (6:12)
Proving FSAs are as Powerful as Regular Expressions (Part 1: Proof Strategy) (4:35)
Proving FSAs are as Powerful as Regular Expressions (Part 2: Bases, Union) (22:55)
Nondeterministic Finite Automata (NFAs) (13:48)
Equivalence of NFAs and DFAs (10:01)
Proving FSAs are as Powerful as Regular Expressions (Part 3: Concatenation) (14:58)
Proving FSAs are as Powerful as Regular Expressions (Part 4: Kleene Star) (8:21)