**TCSS 440/540, Spring 2014**

**Handouts**

- Course
Organization

- Proof by induction (pencast)
- Guide to proof by induction

- Slides: introduction to the course
- Fact 1 and Application
- Proof of Correctness of the Cross Product machine of Theorem 1.25
- Solution
and proof of Suggested Problem #4 on HW #4 (the mod 5 DFA)

- Proof of Correctness of Theorem 1.39
- Subset construction example

- "Drill" questions regarding DFAs, NFAs, regular expressions, and context-free grammars
- Some slides on the pumping lemma for regular languages
- Proof that L(G) = { 0
1^{n}|^{n}*n*³ 0 }. (pencast)

**Assignments**

- General grading scheme (and how scores
translate to a grade for the course)

- Written project (for TCSS 540 students; bonus for TCSS 440 students, due Monday, June 2))
- Homework 1 (due Monday, April 7)
- Homework 2 (due Wednesday, April 16)
- Homework 3 (due Wednesday, April 30)
- Homework 4 (due Wednesday, May 7)
- Homework 5 (due Monday, May 19)
- Homework 6 (due Wednesday, May 28)
- Homework 7 (due Wednesday, June 4)

**Exams**

**On-line resources and fun links:**

- JFLAP - program a finite automaton, PDA, or Turing Machine
- The Theory of Computing Hall of Fame - read about Turing, Chomsky, and other greats
- UW's Steam-Powered Turing Machine