CS341 Automata Theory
Elaine Rich
Schedule of Classes – Fall 2014
Week 
Topics 

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 
Contextfree
grammars 
Tuesday
evening: Midterm 1 
Manipulating
contextfree grammars 


Parse trees 



Ambiguity 

Oct. 14 
Applications
of CFGs 

Pushdown
automata 


Equivalence
of PDAs and CFGs 


Oct. 21 
Contextfree
Pumping Theorem 

Closure
properties of contextfree languages 



Deterministic
contextfree languages 

Oct. 28 
Decision
procedures for contextfree 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 
Other undecidable
problems 

The Chomsky
hierarchy 


THANKSGIVING 


Dec. 2 
Introduction
to complexity 

Review 
