MATH 4805 / MATH 5605 / COMP 4805 in Fall 2010

Instructor

Aaron Williams
haron uvic ca

Assignments

Assignment 1 and solutions
Assignment 2 and solutions
Assignment 3 and solutions

Exams

Midterm and solutions
Final

Lecture Summary

1. Thursday, September 9th.
   • Preliminary Definitions
   • Finite Automata
     • Extended Transition Functions
2. Tuesday, September 14th.
   • Recognizable Languages
     • Finite Strings
     • Prefixes / Suffixes / Substrings
     • Union / Intersection / Complements
3. Thursday, September 16th.
   • Recognizable Languages (continued)
     • Products and Kleene Closure
   • Minimal Automata
     • Inaccessible and Indistinguishable States
     • Partitions and Equivalence Relations
     • The Indistinguishability Relation
4. Tuesday, September 21st.
   • Minimal Automata (continued)
     • Reduced and Accessible Finite Automata
5. Thursday, September 23rd.
   • Minimal Automata (continued)
     • Algorithm for Minimal Finite Automata
6. Tuesday, September 28th.
   • Non-Recognizable Languages
     • The Pumping Property
     • The Pumping Lemma
7. Thursday, September 30th.
   • Non-Deterministic and epsilon-Finite Automata
     • Non-Deterministic Finite Automata
8. Tuesday, October 5th.
   • Non-Deterministic and epsilon-Finite Automata (continued)
     • Subset Construction
     • epsilon-Finite Automata
9. Thursday, October 7th.
   • Non-Deterministic and epsilon-Finite Automata (continued)
     • Removing epsilon-transitions
   • Regular Languages
     • Regular Expressions
     • Kleene's Theorem
10. Tuesday, October 12th.
    • Regular Languages (continued)
      • Kleene's Theorem (continued)
      • Applications

1. Thursday, October 14th.
   • Context-Free Grammars (continued)
     • Derivations / Languages / Sentential Forms
     • Parse Trees
2. Tuesday, October 19th.
   • Context-Free Grammars (continued)
     • Ambiguity
3. Thursday, October 21st.
   • Context-Free Grammars (continued)
     • Normal Forms
4. Tuesday, October 26th. (Taught by Brett Stevens)
   • Context-Free Grammars (continued)
     • Pumping Lemma for Context-Free Languages
5. Thursday, October 28st. (No Class)
6. Tuesday, October 2nd.
   • Pushdown Automata
7. Thursday, November 4th.
   • Pushdown Automata (continued)
     • Equivalence of Final State and Empty Stack
8. Tuesday, November 9th.
   • Pushdown Automata
     • Equivalence with Context-Free Languages
9. Thursday, November 11th.
   • Midterm in class

1. Tuesday, November 16th.
   • Turing Machines
     • IDs and Moves
     • Language
2. Thursday, November 18th.
   • Turing Machines (continued)
     • Accepting vs Deciding
     • Transition Diagrams
3. Tuesday, November 23rd.
   • Turing Machines (continued)
     • Multiple Tapes
     • Non-determinism
     • Church-Turing Thesis
     • Binary Encodings
4. Thursday, November 25th.
   • Decidable and Acceptable Languages
     • Closure Properties
     • Diagonalization Language
5. Tuesday, November 30th.
   • Decidable and Acceptable Languages (continued)
     • Universal Language
     • Reductions
6. Thursday, December 2nd.
   • Decidable and Acceptable Languages (continued)
     • Post's Correspondence Problem
     • P vs NP