Table of Contents

Teaching Materials (Formal Languages and Computation)

While the schedule is suggested so that each of its thirteen segments can be explained during a three-hour class, the lectures correspond to the chapters without any particular time schedule. The lectures also contain additional helpful material, including many examples and figures.

Suggested Thirteen-Week Course Schedule

Lectures (PDF)

The following PDF files contain lectures concerning the topics covered during the thirteen-week course sketched above.

Weeks Topics
Weeks 1 - 2Alphabets, Strings, and Languages (Chapter 2)
Weeks 3 - 4Models for Regular Languages (Sections 3.1 and 3.3)
Restricted Finite Automata (Section 3.2)
Applications: Lexical Analysis (Chapter 4)
Properties of Regular Languages (Chapter 5)
Weeks 5 - 8Models for Context-free Languages (Sections 6.1, 6.3 and 7.1)
Top-Down Parsing (Section 7.2)
Bottom-Up Parsing (Section 7.3)
Properties of Context-free Languages (Section 6.2 and Chapter 8)
Weeks 9 - 13Turing Machines and General Grammars (Section 9.1 and Chapter 11)
Church-Turing Thesis and Turing Machine (Section 9.1)
Restricted Turing Machines (Section 9.2)
Universal Turing Machine (Section 9.3)
Theory of Computation (Section 10.1)
Recursion theorem and Kleene's s-m-n theorem (Section 10.1)
Decidability and Decidable Problems for Finite Automata (Sections 10.2.1 and 10.2.2)
Decidable Problems for Context--Free Grammars (Section 10.2.2)
Undecidable Problems (Section 10.2.3)
General Approach to Undecidability and Computational Complexity (Sections 10.2.3 and 10.2.4)
PDF (complete archive)