CS 476 Automata Theory and Formal Languages Fall 2013 Instructor: Ugur Dogrusoz Office, Hours: EA-522, Tue, Wed AM Classroom, Hours: EB-204, Wed, Fri AM TA, Office Hour: Seher Acer, EA-505, Mon 14:00-15:00

Announcements	HW 3 is now ready due by Dec 31st. Unless otherwise stated, we do not hold the following lecture hour: Wed 8:40-9:30 Check here at least once a week!
Description	Finite automata, regular expressions, regular languages and their properties, the pumping lemma. Context free grammars and languages, normal forms, pushdown automata, the pumping lemma for the CFLs. Turing machines and their properties. Decidability and undecidable languages. Complexity theory, NP-completeness. Credit units: 3 ECTS Credit units: 6, Prerequisite: CS 201.
Textbook	Introduction to the Theory of Computation , 3rd Edition, Cengage Learning, Micheal Sipser
Outline	Introduction and Basics Finite Automata, Regular Expressions and Languages Context-Free Grammars and Languages, and Pushdown Automata Turing Machines, Decidability, and Reducability Complexity Theory and NP-Completeness
Grading	Component Weight Date/Due Attendance/Quiz 20 - Homework 20 HW 1 October 11, 2013 17:00 HW 2 November 18, 2013 17:00 HW 3 December 31, 2013 17:00 Midterm 25 November 18, 2013, 17:45, EB 101-2 Final 35 January 10, 2013, 18:30, EB 101-2
Remarks