| Ders Adı | Kodu | Verildiği Yıl | Verildiği Yarıyıl | Süresi (T+U) | Yerel Kredisi | AKTS Kredisi |
| Biçimsel Diller ve Otomata Teori | CENG 491 | 4 | 1 | 3 + 0 | 3 | 6,00 |
| |
| Ders Bilgileri |
| Dersin Öğretim Dili | İngilizce |
| Dersin Seviyesi | Lisans |
| Dersin Türü | Zorunlu |
| Dersin Veriliş Biçimi | Yüz Yüze |
| |
Dersin Öğrenme Kazanımları:
Bu dersi başarı ile tamamlayan öğrenciler: |
| 1. Sonlu makinaların nasıl çalıştığını anlar |
| 2. Gerekirci ve gerekirci olmayan otomatlarıın eşdeğerliliğini anlar |
| 3. Bağlamdan bağımsız gramerlerin ve aşağı sürüklemeli otomatların denkliğini anlar. |
| 4. Biçimsel dilleri düzenli, bağlamdan bağımsız, Turing karar verilebilir, Turing tanınabilir olarak sınıflandırır. |
| 5. P ve NP sınıflarındaki teorik problemleri analiz eder. |
| |
| Dersin Önkoşulları ve Birlikte Alınması Gereken Dersler | CENG 124 |
| Daha Önce Alınmış Olması Önerilen Dersler | CENG 383 |
| |
Dersin Tanımı:
Formal İspatlar. Sonlu makina, Düzeni ifadeler, ve her iki notasyonu bağlayan algoritmalar. Düzenli diller için Pompalama Ön Önermesi ve düzenli dillerin özellikleri. Bağlamdan bağımsız gramerler. Bağlamdan bağımsız diller için Pompalama Ön Önermesi ve bağlamdan bağımsız dillerin özellikleri. Pushdown makineler ve Turing Makineleri.
|
| |
| Dersin İçeriği (Haftalık Konu Dağılımı): |
| |
| Hafta | Konu |
| 1 | Formal İspatlar |
| 2 | Sonlu otomat |
| 3 | Gerekirci olmayan |
| 4 | Düzenli ifadeler |
| 5 | Düzenli dillerin kapalılık özelliği |
| 6 | Düzenli diller için Pumping savı |
| 7 | Arasınav |
| 8 | Bağlam bağımsız diller ve gramer |
| 9 | Pushdown otomat |
| 10 | Bağlam bağmsız dilleri için Pumping sav |
| 11 | Bağlam hassas diller |
| 12 | Turing makinaları |
| 13 | Turing makina türevleri |
| 14 | Dönem sonu genel gözden geçirme |
| |
| Kaynaklar: |
| J. Hopcroft, R. Motwani, and J. Ullman. Introduction to Automata Theory, Languages, and Computation, Pearson/Addison-Wesley. |
| |
| Diğer Kaynaklar: |
| (1) P. Linz. Introduction to Formal Languages and Automata, 6th edition, 2017 (or 5th or 4th edition), Jones and Barlett; and
(2) Michael Sipser, Introduction to the Theory of Computation, 3rd edition (or 1st edition), 2013, Cengage Learning. |
| |
| Öğretim Yöntem ve Teknikleri: |
| 3 saat teori |
| |
| Değerlendirme Sistemi: |
| Yöntem | Adet | Katkı (%) |
| Ödev | 5 | %30 |
| Ara sınav | 1 | %30 |
| Final sınavı | 1 | %40 |
| |
| Ders İşbaşı Eğitimi (iş yerinde eğitim) Gerektiriyor mu? |
| Gerektirmiyor |