Basic descriptions. Automata and finite automata. Regular Expressions and Languages. Properties of Regular Languages. Context-Free Grammars and Languages. Pushdown Automata. Properties of Context-Free Languages. Introduction to Turing Machines. Undecidability. Intractable Problems.

Midterm - 35%
Homeworks - 20%
Participation - 5%
Final - 40%

(1) Harry R. Lewis, Christos H. Papadimitriou, Elements of the Theory of Computation (2nd Edition), Prentice Hall, 1998.

(1) John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (2nd Edition), Addison Wesley, 2000.
(2) John Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, 2003.
(3) Alexander Meduna, Automata and Languages: Theory and Applications, Springer Verlag, 2000.
(4) Daniel I. A. Cohen, Introduction to Computer Theory, Wiley, 1996.

(1) Introduction, sets, relations and functions
(2) Alphabets, languages and finite representations of languages
(3) Deterministic finite automata 
(4) Nondeterministic finite automata
(5) Equivalent DFA for NFA, FA and regular expressions
(6) Regular and non-regular languages, state minimization
(7) Context-free grammars, parse trees and derivations
(8) Pushdown automata, PDA and context-free grammars
(9) Determinism and parsing, top-down and bottom-up parsing
(10) Turing machines, computing with turing machines
(11) Extensions of Turing machines
(12) Random access Turing machines
(13) Unrestricted grammars, undecidability
(14) The Church-Turing thesis