Instructor: Ganesh Ramakrishnan

Office hours: Mondays and Fridays, 2:00 PM - 3:00 PM

TAs: Chander Iyer (chandler@cse), T.V.S Kiran (tkiran@cse)

Tentative Syllabus

Automata Theory

1. Introduction to Automata Theory.
2. Finite State Automata.
3. Regular Expressions and Languages.
4. Context-Free Grammars and Languages.
5. Pushdown Automata.
6. Turing Machines and Undecidability.

Logic

1. Sets and Relations.
2. Propositional Logic.
3. First-Order Logic.

References

1. Lecture Notes
2. Introduction to automata theory, languages, and computation, Jeffrey D. Ullman
3. Elements of the theory of computation, Harry R. Lewis and Christos H. Papadimitriou
4. Essentials of Theoretical Computer Science (Available Online), F. D. Lewis

Course Notes
Lecture Notes

Course Exercises
Exercises

Homework Solutions
Homework Solutions