CS341  Automata Theory
Elaine Rich

Schedule of Classes – Fall 2014





Aug. 28

Why study automata theory?


What is a language?


Sept. 2

Review of background topics



The big picture



Finite state machines


Sept. 9

Nondeterministic finite state machine


Finite state transducers


Sept. 16

Regular expressions


Equivalence of regular expressions and FSMs


Closure properties of regular languages


Sept. 23

Regular Pumping Theorem


Pumping Theorem and closure


Sept. 30

Functions on regular languages


Decision procedures for regular languages


What is a grammar?


Oct. 7

Context-free grammars

Tuesday evening: Midterm 1

Manipulating context-free grammars


Parse trees





Oct. 14

Applications of CFGs


Pushdown automata


Equivalence of PDAs and CFGs


Oct. 21

Context-free Pumping Theorem


Closure properties of context-free languages



Deterministic context-free languages


Oct. 28

Decision procedures for context-free languages


Turing machines


Multiple tapes and nondeterminism


Nov. 4

Simulating real computers

Tuesday evening: Midterm 2

The Universal Turing machine


Church’s Thesis


Other computational models


The unsolvability of the halting problem


Nov. 11

Decidable and semidecidable languages


Reduction proofs for undecidability


Nov. 18

More on reduction proofs


Rice’s Theorem


Reduction proofs for nonsemidecidability


Nov. 25

More on reduction proofs


Other undecidable problems




Dec. 2

The Chomsky hierarchy