COM1350 Automata Theory Syllabus

Professor Fell

[ Reading | Topics | Grading ]

Text:

  1. Sipser, Michael, "Introduction to the Theory of Computation", PWS Publishing Company, Boston, latest edition.

    Refer to the bibliography in the text for additional reading.

Recommended Reading:

  • Similar Texts:
    1. Harry R. Lewis and Christos H. Papadimitrou, "Elements of the Theory of Computation, Second Edition", Prentice Hall, Upper Saddle River, NJ, 1998.
    2. Daniel I. A. Cohen, "Introduction to Computer Theory, Second Edition", John Wiley & Sons, Inc., New York, 1997.
  • Biography:
    1. Andrew Hodges, "Alan Turing, the enigma", Simon and Schuster, New York, 1983.
  • Light Reading:
    1. David Brin, "Earth", Bantam Books, New York, 1990.
    2. Harry Harrison and Marvin Minsky, "The Turing Option", Warner Books, 1992.
    3. Neal Stephenson "Cryptonomicon", Avon Books, New York, 1999.
    4. Neal Stephenson "The Diamond Age", Bantam Books, New York, 1995.
    5. Neal Stephenson, "Snow Crash", Bantam Books, New York, 1992.
  • Not-So-Light Reading:
    1. Douglas R. Hofstadter, "Gödel, Escher, Bach", Random House, Inc., New York, 1989.

    [ Reading | Topics | Grading ]

    Topics:

    1. Introduction:
      1. Why are we studying theory?
      2. Mathematical Basics
      3. Proofs
    2. Regular Languages
      1. Finite Automata
      2. Nondeterministic Finite Automata
      3. Regular Expressions
      4. Pumping Lemma for Regular Languages
    3. Context-Free Languages
      1. Context-Free Grammars
      2. Pushdown Automata
      3. Pumping Lemma for Context-Free Languages
    4. The Church-Turing Thesis
      1. Turing Machines
      2. Variants of Turing Machines
      3. What is an Algorithm?
    5. Decidability
      1. Decidable Languages
      2. The Halting Problem

    [ Reading | Topics | Grading ]

    Grading:

    1. hour exams: 40 %
    2. problem sets: 25 %
    3. final: 35 %

    Last Updated: March 21, 2002 7:10 a.m. by

    Harriet Fell
    College of Computer Science, Northeastern University
    360 Huntington Avenue #161CN,
    Boston, MA 02115
    Internet: automata@harrietfell.com
    Phone: (617) 373-2198 / Fax: (617) 373-5121
    The URL for this document is: http://www.ccs.neu.edu/home/fell/COM1350/syllabus.html