Formal Languages and Automata Theory

198:452 and 198:508

Spring, 2020

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: Harsha Srimath Tirumala

Email: harsha.tirumala@rutgers.edu

Office: CoRE 246
Office hours for TA: Mondays and Fridays 2:30-3:30 (and other times by appointment)

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.
(Also, here are some helpful Guidelines from the TA.)

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

The class meets in TIL 116 (on the Livingston Campus), Tuesdays and Thursdays, 3:20-4:40.

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, March 3.
7 lectures: Computability Theory, Undecidability, Turing Machines
10 lectures: Complexity Theory

There will be weekly homework assignments, and there will also be one final examination. (Probably this will be a take-home final exam.) 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.