COM 1350 Automata and Formal Languages

Course Description and Catalog Information
Course Information (links to past and current course materials)
Course Format
Course Coordinator
Textbooks and References
Course Goals
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

    Textbooks and References

    Spring 2000

    Course Goals

    To learn about the theoretical model for computation.

    Prerequisites by Topic

    Major Topics Covered in the Course

    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).