**THEORY OF COMPUTING
Com S 331**

**Course Topics**

The following is a

tentativeschedule of the topics we will be covering in class.

Date Book Chapters Topics Jan 13 - Introduction and Course Policies Jan 15 Kozen 2 Alphabets, Strings and Languages Jan 17 Kozen 2 Operations on Strings and Languages Jan 20 - University Holiday Jan 22 Kozen 2 Operations on Strings and Languages Jan 24 LP 1.4 - 1.5 Pigeon-hole Principle, Dovetailing Jan 27 LP 1.4 - 1.5 Dovetailing, Diagonalization Jan 29 Kozen 3 Deterministic Finite Automata Jan 31 Kozen 4 Regular Languages Feb 3 Kozen 4 Closure Properties of Regular Languages Feb 5 Kozen 5 Non-determinism Feb 7 Kozen 5 Non-deterministic Finite Automata Feb 10 Kozen 6 Subset Construction Feb 12 - Power of NFAs Feb 14 Kozen 6 Epsilon Transitions

More Closure Properties of Regular LanguagesFeb 17 Kozen 7 Pattern Matching Feb 19 Kozen 8 Patterns and Regular Expressions Feb 21 Kozen 9 Regular Expressions and Finite Automata Feb 24 - Exam I Feb 26 Kozen 9 Converting NFAs to Regular Expressions Feb 28 Kozen 11 Non-regular Languages

Pumping Lemma for Regular LanguagesMar 3 Kozen 12 Using the Pumping Lemma to Prove Non-regularity Mar 5 Kozen 10 Homomorphisms

Using Closure Properties to Prove Non-regularityMar 7 - Constructing NFAs by Modifying Existing NFAs Mar 10 Kozen 19 Context-Free Languages and Grammars: Definitions Mar 12 Kozen 19 Context-Free Languages and Grammars: Examples Mar 14 Kozen 20 Balanced Parentheses Mar 17 - Spring Break Mar 19 - Spring Break Mar 21 - Spring Break Mar 24 Kozen 21 Chomsky and Greibach Normal Forms Mar 26 Kozen 21 Eliminating Epsilon and Unit Productions

Derivation TreesMar 28 - Ambiguous and Linear Grammars Mar 31 Kozen 22 Pumping Lemma for Context-Free Languages Apr 2 Kozen 22 Using the Pumping Lemma to Prove Non-Context-Freedom Apr 4 Kozen 27 Closure Properties of Context-Free Languages Apr 7 - Exam II Apr 9 Kozen 23 Pushdown Automata: Definitions Apr 11 Kozen 23 Pushdown Automata: Examples Apr 14 - Deterministic Pushdown Automata Apr 16 - Deterministic CFLs are Unambiguous Apr 18 Kozen 28 Turing Machines: Definitions Apr 21 Kozen 29 Turing Machines: Examples Apr 23 Kozen 29 Turing Machines: Examples Apr 25 Kozen 29 Acceptable and Decidable Languages Apr 28 Kozen 31 The Universal Turing Machine and The Halting Problem Apr 30 Kozen 31 Proving Undecidability Using Diagonalization May 2 Kozen 32 Proving Undecidability Using Machine Constructions Iowa State University - Computer Science Department - Top of this page