# COMP 330 Theory of Computation

## Lecture notes

Subject | Semester |
---|---|

## Tuesday, September 3, 2013Introduction to the course |
Fall 2013 |

## Thursday, September 5, 2013DFAs for determining validity of words |
Fall 2013 |

## Tuesday, September 10, 2013Nondeterministic finite automata |
Fall 2013 |

## Thursday, September 12, 2013Constructions on languages and regular expressions |
Fall 2013 |

## Tuesday, September 17, 2013Minimisation theory for DFAs |
Fall 2013 |

## Thursday, September 19, 2013Learning algorithms (optional material) |
Fall 2013 |

## Tuesday, September 24, 2013Right invariance, isomorphisms |
Fall 2013 |

## Thursday, September 26, 2013Behaviour of finite state systems |
Fall 2013 |

## Tuesday, October 1, 2013The pumping lemma |
Fall 2013 |

## Thursday, October 3, 2013More pumping lemma stuff |
Fall 2013 |

## Tuesday, October 8, 2013Duality |
Fall 2013 |

## Thursday, October 10, 2013Midterm |
Fall 2013 |

## Tuesday, October 15, 2013Context-free languages |
Fall 2013 |

## Thursday, October 17, 2013Pushdown automata |
Fall 2013 |

## Tuesday, October 22, 2013The pumping lemma for CFLs |
Fall 2013 |

## Thursday, October 24, 2013Algorithms for CFLs |
Fall 2013 |

## Tuesday, October 29, 2013Turing machines |
Fall 2013 |

## Thursday, October 31, 2013Lambda calculus (optional material) |
Fall 2013 |

## Tuesday, November 5, 2013The halting problem and undecidability |
Fall 2013 |

## Thursday, November 7, 2013Reductions and PCP |
Fall 2013 |

## Tuesday, November 12, 2013The structural theory of computability |
Fall 2013 |

## Thursday, November 14, 2013Limitations of CFLs |
Fall 2013 |

## Tuesday, November 19, 2013Validity in first-order logic |
Fall 2013 |

## Thursday, November 21, 2013Universal computable functions |
Fall 2013 |

## Tuesday, November 26, 2013Recursion theorem |
Fall 2013 |

## Thursday, November 28, 2013GĂ¶del's incompleteness theorem (optional material) |
Fall 2013 |

## Summary

Subject | Semester |
---|---|

## Midterm review |
Fall 2013 |

## Final review |
Fall 2013 |