Temel tanımlar, otomat ve sonlu otomat, düzenli ifadeler ve formal diller, düzenli dillerin özellikleri, içerikten bağımsız grammerler ve diller, pushdown otomat, içerikten bağımsız dillerin özellikleri, Turing makinelerine giriş, karar verilemeyen problemler, zor problemler.

Arasınav - 35%
Ödevler - 20%
Katılım - 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) Giriş
(2) Alfabeler ve diller
(2) Deterministik ve nondeterministik otomat 
(3) Düzenli ifadeler
(4) Sonlu otomat ve düzenli ifadeler
(5) Durum minimizasyonu
(6) İçerikten bağımsız gramerler, parse ağaçları
(7) Pushdown otomat
(8) Pushdown otomat ve içerikten bağımsız gramerler
(9) Turing makineleri
(10) Gelişmiş Turing makineleri
(11) Church-Turing tezi

•  Introduction, sets, relations and functions - Sunum dosyası
•  Alphabets, languages and finite representations of languages - Sunum dosyası
•  Deterministic finite automata - Sunum dosyası
•  Nondeterministic finite automata - Sunum dosyası
•  Equivalent DFA for NFA, FA and regular expressions - Sunum dosyası
•  Regular and non-regular languages, state minimization - Sunum dosyası
•  Context-free grammars, parse trees and derivations - Sunum dosyası
•  Pushdown automata, PDA and context-free grammars - Sunum dosyası
•  Determinism and parsing, top-down and bottom-up parsing - Sunum dosyası
•  Turing machines, computing with turing machines, extensions of Turing machines - Sunum dosyası
•  Random access Turing machines, unrestricted grammars, undecidability, The Church-Turing thesis - Sunum dosyası