COMP 3413 X1 − Fall 2006

Formal Languages, Automata and Computation

Classes: 14:30-16:00 Mon-Wed

Classroom: CAR 113

Instructor: Andrei Gagarin

Office: CAR 411

E-Mail: andrei.gagarin@acadiau.ca

Office Hours: 15:00-16:00 Tue, 16:00-17:00 Fri

Course Webpage:

Some course materials
will be available on ACME: __http://acme.acadiau.ca__

Course Objectives:

This course will provide an introduction to the following topics:

ü Regular languages: finite automata, regular expressions, closure properties;

ü Context-free languages: context-free grammars, pushdown automata, closure properties;

ü Turing machines and computability: recursive and recursively enumerable languages, decidability and undecidability;

ü Elements of computational complexity theory.

Textbooks:

Required:

J. Hopcroft, R. Motwani, and J. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison-Wesley, 2006.

Secondary references (recommended):

J. Martin, Introduction to Languages and the Theory
of Computations, 3^{rd} Edition, McGraw-Hill (available at the
bookstore).

P. Linz, An Introduction to Formal Languages and
Automata, 4^{th} Edition, Jones and Bartlett Publishers, 2006 (will be
available at the library).

Course Evaluation:

Four Assignments 40%

Midterm 20%

Final Exam 40%

Academic Integrity

Please, read the relevant section of the undergraduate calendar on Academic Integrity. It will be strictly enforced. In particular:

· If you copy a solution to an assignment question, you are guilty of an academic offense. This includes solutions from classmates, the Internet, or textbooks.

· If you use any unauthorized resources during the midterm or the final exam, you are guilty of an academic offense.

· If you knowingly help a classmate to cheat, you are guilty of an academic offense.

The penalties for cheating are:

· For the first offense: you will receive -100% for the assignment/exam. In addition your mark will be truncated to B (about 70%).

· For the second offense: you will receive a mark of 0% for the course.