| Dersin Amacı | Bu dersin amacı, öğrencilere, otomata teorisi ve biçimsel diller ve gramerler teorisini içeren hesaplamanın matematiksel temellerini tanıtmak; aynı zamanda otomatlar, eşdeğer düzenli ifadeler, otomatlar tarafından tanımlanan dillerin eşdeğerliği, düzenli ifadeler, pushdown otomatı, eşdeğer context-free gramerleri, pushdown otomata tarafından tanımlanan dillerin eşdeğeri, bağlam gibi temel kavramları kavratmaktır. ücretsiz gramerler, Turing makineleri ve Turing makineleri tarafından tanımlanan dillerin eşdeğerliği. |
|---|
| Dersin İçeriği | Dersin İçeriği Matematiksel Araçlar (Tanımlar, Teoremler ve İspatlar); İspat Türleri; Düzenli Diller; Sonlu Otomatlar; Deterministik Olmayan Makinalar; Düzenli İfadeler; Düzensiz Diller; Bağlam İçermeyen (Context-free) Diller; Bağlam İçermeyen (Context-free) Gramerler; Basma Otomatiği; Turing Makineleri; Turing Makinelerinin Çeşitleri; "Algoritma" tanımı; Karar Verebilirlik; Kararlanabilir Diller; NP-bütünlüğü; İndirgenebilirlik; Tanınabilirlik.
|
|---|
| Ders Kitabı / Malzemesi / Önerilen Kaynaklar | - Michael Sipser, Introduction to the Theory of Computation, Cengage Learning, 3rd Edition, 2012
- Daniel I. A. Cohen, Introduction to Computer Theory, Prentice-Hall, 2nd Edition, 1997
|
|---|
