The syllabus for this course is here.
I talked about finite automata.
Reading is section 1.1.
I introduced NFAs and showed that NFAs are equivalent to DFAs. You should begin reading section 1.2
I showed that regular set operations preserve regularity of languages and that languages are regular if and only if they can be described by regular expressions. Reading is up through the end of section 1.3.
Exercises 1.6 a,b,d,e,f; 1.7 d, e; 1.14; 1.16; 1.31; 1.32. These problems are due on Wednesday, April 9.
Section 1.4, pumping lemma.
Sections 2.1 and 2.2
Exercises 1.21, 1.29b, 1.30, 1.46a, 1.49, 2.4be, 2.5be, 2.13. These problems are due on Monday, April 14.
Section 2.3
2.21, 2.30ad, 2.31. These problems are due on Friday, April 18.
I began the discussion of Turing Machines and showed some examples. Reading is section 3.1.
Section 3.2.
Exercises 3.7, 3.8b, 3.11, 3.14, and 3.16b. These problems are due on Friday, April 25.
Section 4.1 - Decidable languages
The first midterm exam is coming up on Wednesday, April 23. The exam will cover chapters one and two. Specific topics to study for the exam include:
Due Friday, May 2
4.3, 4.14, 4.16, 4.28
Section 4.2
Section 5.1 - Undecidable problems
Sections 5.2 and 5.3. I also showed the solution to problem 5.20.
Due Wednesday, May 7
Give problem 4.14 another shot, by proving the following result. If G is a CFG and L(G) is a subset of 1* there exists an N such if all strings with length less than or equal to N in 1* are in L(G), then L(G) = 1*.
In addition to this, please also do problems 5.4, 5.9, 5.23, 5.30b, and 5.31.
I went over Rice's theorem (problem 5.28) and started in on section 6.1.
I finished section 6.1.
Section 6.2
6.6, 6.7, and 6.13. These problems are due on Monday, May 19.
Section 7.1
Sections 7.2 and 7.3
Sections 7.4, 7.5, and 10.1
7.9, 7.11, 7.20, 7.27, and 7.29. These problems are due on Wednesday, June 4.
I discussed parsing algorithms for context free languages.