Course Outline

Instructor: Michael Winter, Office J323, Office J323, Office Hours: Mon & Fri, 10:00am-noon, email:

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

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.


COSC Home Page
COSC/MATH 4P61 Home Page
© M. Winter, 2015