Syllabus

Catalog Description

Formal languages; finite automata and regular expressions; properties of regular languages; pushdown automata and context-free grammars; properties of context-free languages; introduction to computability and unsolvability (Turing machines) and computational complexity.

Prerequisites

Computer Science 40; open to computer science and computer engineering majors only.

Course Goals

The goals of this course are to:
  1. introduce you to the need for, and the working of, mathematical proof;
  2. develop facility with the concepts, notation, and techniques of the theories of automata, formal languages, and Turing machines;
  3. give a historical perspective of the creation of the computer, and an understanding of some of its capabilties and limitations.
I believe that the future belongs to those who enjoy learning things for themselves.  I consequently hope that you explore on your own some additional topics that are of interest to you . Self-directed learning, like any skill, takes practice.  Persevere. Self-directed learning does not mean that you cannot talk to people. It means that you take personal responsibility for organizing and executing---in a word, directing---your own learning plan.

As an instructor, my goal is to encourage you to become a more self-directed learner.

Why have an upper division course on automata & formal languages?

Aspects of automata theory and formal languages are valuable tools in a variety of disciplines. The theoretical, mind-expanding exercises in this course retain their value, regardless of how practical your particular interests may be.

Contributions to educational objectives (to be fixed)

This course contributes directly to the following educational goals:
S4: communicate effectively.
and indirectly to:
S2: recognize the need for, and expect to engage in, life-long learning for continued effectiveness in the profession.
S9: have the knowledge and capability that prepares them to be highly trainable in the job market

Relevance to Program (to be fixed)

Course 
Goals		 Mapping to 
Educational Objectives		 Contibution to 
Program Goals*
1
S9
5
2
S6, S9
5
3
S6
2
* Scale: 1 is Low and 5 is High

Workload

This is a 4-credit course at UCSB.  You are expected to finish this course in 10 weeks, working intelligently for an average of 10 hours/week.

Discussions & Lectures

Please email Peter Cappello comments about what you would like to see in future lectures, so that he can better accommodate your wishes.

Required Text

textbook cover

Peter Linz. An Introduction to Formal Languages and Automata (3rd edition), Jones and Bartlett, Incorporated, 2001, Library of Congress: QA267.3.L56 2000; ISBN: 0-7637-1422-4.