### CS 541 Introduction to Automata Theory
and Formal Languages
Fall 1999
** Brief Description.** This course is divided into three main parts:
finite automata, context-free languages and Turing machines. Below are
some of the topics that will be studied.
- Finite automata: deterministic and nondeterministic, regular expressions,
Pumping Lemma
- Context-free languages: context-free grammars, Chomsky Normal Form,
pushdown automata, Pumping Lemma
- Turing machines: deterministic and nondeterministic, variants, undecidability
** Instructor.** Alexis Maciel. Science Center 379, 268-2385, alexis@clarkson.edu.
** Office Hours.** Monday and Wednesday 4:00-5:00, Tuesday and Thursday
3:30-5:00, and by appointment.
** Required Text. **
Michael Sipser, * Introduction to the Theory of Computation*, PWS
Publishing Company, Boston, MA, 1997.
We will cover at least Chapters 1 to 4 and parts of 5.
** Grading. **
Homework assignments |
30% |
Two tests |
30% |
Final exam |
40% |
The assignment policy for the course will be stated on the first assignment.
Tentative dates for the tests: October 15 and November 19. |