COM 1350 Automata and Formal Languages

Course Format
Course Coordinator
Textbooks and References

Prerequisites by Topic
Major Topics Covered in Course
Laboratory Projects

Course Description

Covers finite-state machines and regular expressions; context-free grammars; properties and decidability problems of regular and context-free languages; pushdown automata; pumping theorems for regular and context-free languages; Turing machines, Church's thesis, and the halting problem; and applications to compilers, artificial intelligence, and pattern recognition.

4 QH credit
Prerequisite: COM 1201, COM 1340, and MTH 1137.

Course Information

Course is offered during the Spring and Summer quarters. CS majors are guaranteed a place in class.
 

Spring 2001

Summer 2001

Course Format

BSCS03 required course
BSCS04 Languagecore
BACS required core
BSIS general elective

This is a BS CS Languages core and is a required course for BA CS majors.

Course Coordinators

Professor Harriet Fell
fell@ccs.neu.edu

Textbooks and References

Spring 2000

• Michael Sipser, "Introduction to the Theory of Computation", PWS Publishing Company, Boston, 1997 (reprinted later with corrections).

 
References

Similar Texts
 

• Harry R. Lewis and Christos H. Papadimitrou, "Elements of the Theory of Computation, Second Edition", Prentice Hall, Upper Saddle River, NJ, 1998.
• Daniel I. A. Cohen, "Introduction to Computer Theory, Second Edition", John Wiley & Sons, Inc., New York, 1997.

 
Biography
 
• Andrew Hodges, "Alan Turing, the enigma", Simon and Schuster, New York, 1983.

 
Light Reading
 
• David Brin, "Earth", Bantam Books, New York, 1990.
• Harry Harrison and Marvin Minsky, "The Turing Option", Warner Books, 1992.
• Neal Stephenson The Diamond Age", Bantam Books, New York, 1995.
• Neal Stephenson, "Snow Crash", Bantam Books, New York, 1992.

 
Not-So-Light Reading
 
• Douglas R. Hofstadter, "Goedel, Escher, Bach", Random House, Inc., New York, 1989.

Course Goals

To learn about the theoretical model for computation.

Prerequisites by Topic

Logic
 
• boolean logic and sets
• sequences and tuples
• functions and relations
• propositional logic
• predicate logic
• use of proof techniques: induction, contradiction, direct proof

They should have seen the things above but will get more practice in this course.

Discrete math
 

• counting, principle of inclusion and exclusion
• recursive definition
• basic graph theory and algorithms

They should have seen the things above but will get more practice in this course.  They really should understand breath-first search.

Major Topics Covered in the Course

Automata theory:
 
• automata, finite state machines
• regular expressions
• languages and grammars
• Turing machine as a formal definition of algorithm
• decidability, halting problem

Role of theory  in decision making:

In particular, understanding that some problems may not be tractable but that an acceptable solution may come out of heuristics or probabilistic algorithms.

Laboratory projects

There are no programming assignments (except for the honors adjunct).
There are four homework assignments, three hour exams, and a final.
This will change as students enter the course with the knowledge of Scheme (new prerequisite course COM 1340).