CS341  Automata Theory
Elaine Rich

Schedule of Classes

 

Week

Topics

 

Aug. 27

Why study automata theory?

 

What is a language?

 

Sept. 1

The big picture

 

Finite state machines

 

Nondeterministic finite state machines

 

Sept. 8

Finite state transducers

 

Regular expressions

 

Equivalence of regular expressions and FSMs

 

Sept. 15

Closure properties of regular languages

 

Regular Pumping Theorem

 

Pumping Theorem and closure

 

Sept. 22

Functions on regular languages

 

Decision procedures for regular languages

 

Review of regular languages

 

Sept. 29

Context-free grammars

Tuesday evening: Midterm 1

Manipulating context-free grammars

 

Parse trees

 

Ambiguity

 

Oct. 6

Pushdown automata

 

Equivalence of PDAs and CFGs

 

Oct. 13

Context-Free Pumping Theorem

 

Closure properties of context-free languages

 

Oct. 20

Decision procedures for context-free languages

 

Turing machines

 

Multiple tapes and nondeterminism

 

Oct. 27

Simulating real computers

Tuesday evening: Midterm 2

The Universal Turing machine

 

Church’s Thesis

 

Other computational models

 

Nov. 3

The unsolvability of the halting problem

 

Decidable and semidecidable languages

 

Reduction proofs for undecidability

 

Nov. 10

More on reduction proofs

 

Rice’s Theorem

 

Nov. 17

Reduction proofs for nonsemidecidability

 

Other undecidable problems

 

The Chomsky hierarchy

 

Nov. 24

Introduction to complexity theory

 

Measuring time and space complexity

 

P and NP

 

THANKSGIVING

 

Dec. 1

Using reduction for complexity

 

The Cook-Levin Theorem

 

Other NP-complete problems