Formal Languages and Automata Theory

198:452 and 198:508

Spring, 2017

Professor Eric Allender

Phone: (848) 445-7296
FAX: (732) 445-0537

Email: allender@cs.rutgers.edu

Office: Hill 442
Click here for current Office Hours.

Teaching Assistant: Malihe Alikhani

Email: ma1195 AT cs.rutgers.edu

Office: Hill 410
Office hours for TA: Fridays, 1:30-3:00

Text: Michael Sipser, Introduction to the Theory of Computation. Please also take note of the list of errata for the textbook.

Click here to find out about what was covered in class, and what material you should read next.

Click here to find out about homework.

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

The class meets in BRR 5085 (The Business School, on the Livingston Campus), Tuesdays and Fridays noon-1:20 PM.

ROUGH COURSE OUTLINE

4 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 on Tuesday, February 21.
7 lectures: Computability Theory, Undecidability, Turing Machines
10 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.

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.