COSC/MATH 4P61 Course Outline

Instructor: Michael Winter, Office J323, Office J323, Office Hours: Mon & Fri, 10:00am-noon, email: mwinter@brocku.ca

Calendar description

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.

Course Outline

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

^* October 12-16 is Fall Reading Week, no classes.

Texts

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