##
Course Outline |
||

Regular languages and finite state machines: deterministic and non-deterministic machines, Kleene's theorem, the pumping lemma, Myhill-Nerode Theorem and decidable questions. Context-free languages: generation by context-free grammars and acceptance by pushdown automata, pumping lemma, closure properties, decidability. Turing machines: recursively enumerable languages, universal Turing machines, halting problem and other undecidable questions.

Week |
Date |
Topics |

1 | Sep 10 | Introduction, Formal Languages and Computability |

2 | Sep 17 | Finite Automata & Regular Languages: Definition, Kleene's Theorem |

3 | Sep 24 | Finite Automata & Regular Languages: Minimalization, Closure Porperties, Pumping Lemma for Regular Languages |

4 | Oct 01 | Context-Free Languages, CFG's, Parse-Trees, Normal Forms of CFG's (Test 1) |

5 | Oct 08 | Pushdown Automata, Equivalence for PDA's and CFG's, Pumping Lemma for Context-Free Languages |

6^{*} |
Oct 22 | Turing Machines, Universal Turing Machines |

7 | Oct 29 | Context-Sensitive Languages |

8 | Nov 05 | Recursively Enumerable Languages (Test 2) |

9 | Nov 12 | Undecidable Problems, Halting Problem |

10 | Nov 19 | Partial Recursive Functions, Primitive Recursive Functions |

11 | Nov 26 | Complexity (Test 3) |

12 | Dec 03 | Complexity, P vs. NP |

- John E. Hopcroft, Rajeev Motwani, and Jeffrey Ullman: Introduction to Automata Theory, Languages, and Computation (3rd ed.), Addison-Wesley (2007).

COSC/MATH 4P61 Home Page