MET CS 662 Computer Language Theory
"Nothing is more practical than a good theory"
Sign up for the interactive classroom to view your scores, submit homework,
or simply chat about topics discussed in class. All you need is request
an account by accessing the Interactive
Classroom and clicking at the 'Request an Account' button under the
'Student' heading.
Course Objectives
The goal of this course is to provide solid knowledge of the fundamental
concepts and methods of the theory of computation, and to outline some
research trends. Two different approaches for "capturing" the idea of computing
in a formal mathematical way are discussed  finite state machines and
grammars. At the end of the course students will be able to interprete,
relate and apply the basic concepts of the theory of computation to problems
from different areas of computer science.
Course Overview
We will focus on two distinct and equivalent computing paradigms
 finite state machines, and, rewriting rules or grammars. Each paradigm
is first introduced in its simplest form and gradually generalized. We
will proceed from deterministic finite automata, regular expressions and
grammars to push down automata and context free grammars, and finally to
Turing machines and general grammars. The languages defined (recognized
or accepted) by the two formalisms and the relations between them
are presented in the framework of the Chomsky hierarchy. A discussion of
the ChurchTuring thesis and its implications summarizes our present knowledge
of a "mechanical" computation. The course ends with an outlook to the topics
of uncomputability/undecidability and untractable problems.
Prerequisites
MET CS 566 Algorithms.
Course Format and Grading Policy
New material will be presented in lecture format. Reviews, exercises and
homework solutions will take place in discussion. Participation in the
discussions, although not mandatory, is strongly recommended and may result
in extra credit.
Weekly mandatory homework, a midterm and a final examination will provide
the basis for the grade. Homeworks are due one week after handed out. Late
homework will not be accepted unless permission by the instructor was given
prior to the due date.
No predetermined scale will be used. The final grade will be assigned
based on the following weighting

Homework 40%

Midterm 25%

Final 35%

Optional Project
Cheating and plagiarism will not be tolerated. They will result in no credit
for the homework or examination. This should not be understood as a discouragement
for discussing the material or your particular approach to a problem with
other students in the class. On the contrary  I urge you to share your
thoughts, questions and solutions. Naturally, if you choose to work in
a group, I will be expecting more than one and highly original solutions
rather than the same mistakes.
Texts
P. Linz. An Introduction to Formal Languages and Automata. D.C.
Heath and Co, 1990 (required).
H. R. Lewis, C. H. Papadimitriou. Elements of the theory of computation.
PrenticeHall, 1998 (optional).
Additional reading lists on specific topics will be distributed throughout
the semester. A good reference book for the theoretically incled
student is J. E. Hopcroft, J. D. Ullman. Introduction to automata theory,
languages and computation. Addison Wesley, 1979.
Course Information

Time: Tuesday, 69 p.m.

Place: FLR 133

Instructor: Tanya Zlateva, Ph.D., Assoc. Prof.

Office Hours: Tuesday, 56 p.m. and by appointment

Office Address: 808 Commonwealth Ave., Room 250. Boston, MA 02215.

Telephone: 6173532568

Email: zlateva@bu.edu

web:http://bumetb.bu.edu/~zlateva/

Fax: 6173532367
Page prepared by Tanya Zlateva