COM 3710: Automata and Formal Languages

Winter 2003

Instructor:  Rajmohan Rajaraman

113 Cullinane Hall                                                                      Work: 617-373-2075
College of Computer Science                                                 Email: rraj@ccs.neu.edu
Northeastern University                                                           Home: 617-232-8298
Boston, MA 02115                                                                     Fax:    617-373-5121

Class meeting times/location:     W 6:00-9:00, 39 CN

Office Hours:    W 12:00--1:00 and M 4:30--5:30


Course Description

Textbook

Grading

Administrivia

Course Information
Tentative Course Schedule
Questionnaire
Problem Sets

          Problem Set 1
          Problem Set 2
          Sample Solution to PS1
          Problem Set 3
          Sample Solution to PS2
          Sample Solution to PS3

POWs

          POW-1
          POW-2
          POW-3 and 4
          POW-5
           Sample solution to POW-3
         POW-6 and 7
         POW-8
         POW-9, 10 and 11
         Sample solution to POW-8 (in MS Word)
            POW-12-14
         POW-15-19

Midterm

(All handouts are in postscript format, unless otherwise noted.)

Course Description

This course provides a graduate-level introduction to the theory of automata and formal languages.  We will study basic models of computation including finite automata,
context-free grammars, and Turing machines, and will explore the fundamental capabilities and limitations of computers.
 

Required Textbook

A list of errata is available from a webpage maintained by the author.  We will cover Chapters 1 through 5 of Sipser's book.  In addition, we will cover selected topics from other sources.  Two useful reference books for this course are the following:

Grading

The course grade will be based on four problem sets (total 30%), a midterm (25%), a final exam (40%), and class participation (5%).

Problem Sets


Problem sets are due at the beginning of class. As a general rule, any problem set turned in up to 1 week late will be penalized 20%, and no homework will be accepted beyond 1 week past its due date.    Students may discuss the problem sets with one another, but solutions should be written up separately.  If a key idea is
obtained from another person (other than the instructor) or from another book or paper (other than the course textbook), then the source of that idea should be cited.  Solutions should be presented in a clear and concise manner.  Here are the tentative dates on which problem sets will be handed out/due: Jan 8/Jan 22, Jan 22/Jan 29, Jan 29/Feb 12, and Feb 19/Mar 5.

Class Participation

In each class, a ``Problem of the Week'' (or two) will be handed out, and a student will be called on to present his/her solution to the problem in the following class. Everbody is required to present at least once during the course.  The grade for class participation will be based on the quality of the presentation and participation in class discussions.

Exams

The midterm will probably be a take-home exam that will be given out on Wednesday, Feb 12 and due the following Monday, Feb 17.  The final exam will be an in-class exam and will
take place during finals week.