Aaron Williams

haron uvic ca

Assignment 1 and solutions

Assignment 2 and solutions

Assignment 3 and solutions

Midterm and solutions

Final

- Thursday, September 9th.
- Preliminary Definitions
- Finite Automata
- Extended Transition Functions

- Tuesday, September 14th.
- Recognizable Languages
- Finite Strings
- Prefixes / Suffixes / Substrings
- Union / Intersection / Complements

- Recognizable Languages
- Thursday, September 16th.
- Recognizable Languages (continued)
- Products and Kleene Closure

- Minimal Automata
- Inaccessible and Indistinguishable States
- Partitions and Equivalence Relations
- The Indistinguishability Relation

- Recognizable Languages (continued)
- Tuesday, September 21st.
- Minimal Automata (continued)
- Reduced and Accessible Finite Automata

- Minimal Automata (continued)
- Thursday, September 23rd.
- Minimal Automata (continued)
- Algorithm for Minimal Finite Automata

- Minimal Automata (continued)
- Tuesday, September 28th.
- Non-Recognizable Languages
- The Pumping Property
- The Pumping Lemma

- Non-Recognizable Languages
- Thursday, September 30th.
- Non-Deterministic and epsilon-Finite Automata
- Non-Deterministic Finite Automata

- Non-Deterministic and epsilon-Finite Automata
- Tuesday, October 5th.
- Non-Deterministic and epsilon-Finite Automata (continued)
- Subset Construction
- epsilon-Finite Automata

- Non-Deterministic and epsilon-Finite Automata (continued)
- Thursday, October 7th.
- Non-Deterministic and epsilon-Finite Automata (continued)
- Removing epsilon-transitions

- Regular Languages
- Regular Expressions
- Kleene's Theorem

- Non-Deterministic and epsilon-Finite Automata (continued)
- Tuesday, October 12th.
- Regular Languages (continued)
- Kleene's Theorem (continued)
- Applications

- Regular Languages (continued)

- Thursday, October 14th.
- Context-Free Grammars (continued)
- Derivations / Languages / Sentential Forms
- Parse Trees

- Context-Free Grammars (continued)
- Tuesday, October 19th.
- Context-Free Grammars (continued)
- Ambiguity

- Context-Free Grammars (continued)
- Thursday, October 21st.
- Context-Free Grammars (continued)
- Normal Forms

- Context-Free Grammars (continued)
- Tuesday, October 26th. (Taught by Brett Stevens)
- Context-Free Grammars (continued)
- Pumping Lemma for Context-Free Languages

- Context-Free Grammars (continued)
- Thursday, October 28st. (No Class)
- Tuesday, October 2nd.
- Pushdown Automata

- Thursday, November 4th.
- Pushdown Automata (continued)
- Equivalence of Final State and Empty Stack

- Pushdown Automata (continued)
- Tuesday, November 9th.
- Pushdown Automata
- Equivalence with Context-Free Languages

- Pushdown Automata
- Thursday, November 11th.
- Midterm in class

- Tuesday, November 16th.
- Turing Machines
- IDs and Moves
- Language

- Turing Machines
- Thursday, November 18th.
- Turing Machines (continued)
- Accepting vs Deciding
- Transition Diagrams

- Turing Machines (continued)
- Tuesday, November 23rd.
- Turing Machines (continued)
- Multiple Tapes
- Non-determinism
- Church-Turing Thesis
- Binary Encodings

- Turing Machines (continued)
- Thursday, November 25th.
- Decidable and Acceptable Languages
- Closure Properties
- Diagonalization Language

- Decidable and Acceptable Languages
- Tuesday, November 30th.
- Decidable and Acceptable Languages (continued)
- Universal Language
- Reductions

- Decidable and Acceptable Languages (continued)
- Thursday, December 2nd.
- Decidable and Acceptable Languages (continued)
- Post's Correspondence Problem
- P vs NP

- Decidable and Acceptable Languages (continued)