Formal Languages and Automata Theory

198:452

Section 1, Spring, 2006

Professor Eric Allender

Phone: (732) 445-3629
FAX: (732) 445-0537

Email: allender@cs.rutgers.edu

Office: Hill 442
Click here for current Office Hours.

Teaching Assistant: Bin Tian

Phone: (732) 445-6595

Email: tian (at) cs (dot) rutgers (dot) edu

Office: Hill 415
Office hours for TA: Wednesdays, 10:00-noon

Text: Michael Sipser, Introduction to the Theory of Computation.

Click here to find out about homework.

Prerequisites: 205 and 344, or familiarity with induction, dynamic programming, and basic algorithms.

ROUGH COURSE OUTLINE

6 lectures: Regular Languages, Finite Automata, Regular Expressions and Grammars
6 lectures: Context-Free Languages and Grammars, Pushdown Automata.
A MIDTERM will be taken during class after this section.
7 lectures: Computability Theory, Undecidability, Turing Machines
8 lectures: Complexity Theory

There will be weekly homework assignments, and there will also be one take-home final examination. The homework and the final exam have almost equal weight, and together they account for almost ninety percent of the final grade.

It sometimes happens that there is a large number of graduate students in the class. Undergraduates should note that, in determining the ``curve,'' I take only the undergraduate population into consideration; grad students are assigned grades only after I have already awarded grades to the undergrads.

No collaboration or discussion of questions on the final exam is allowed (other than discussion with me). In contrast, I have no objection to your discussing the homework problems among yourselves (as well as with me). However, this discussion should be limited to an exchange of ideas concerning what approaches do and do not work. Under no circumstances should you show your work to any other student, or in any other way provide detailed information concerning your solutions.