Ders hakkında soru ve önerilerinizi inanhoca@gmail.com adresine yollayabilirsiniz.
Özdevinirler (otomatlar) kuramı ve biçimsel diller, bilgisayar bilimleri ve mühendisliğinin kuramsal temelleri alanının en önemli konularından biridir. Bu nedenle bilgisayar bilimleri ve bilgisayar mühendisliği alanında eğitim veren lisans programlarının birçoğunda bu konunun işlendiği bir derse yer verilmektedir. Özdevinirler ya da otomatlar denince akla ilk gelen, kendi kendine hareket eden ve belirli işlevleri gerçekleştiren otomatik makineler olmaktadır. Özdevinir yerine kısaca makine sözcüğünün kullanılmasının nedeni de budur. Oysa bilimsel olarak, özdevinirler belirli özelliklere sahip matematiksel modellerdir. Bu modeller yalnız donanım alanında değil, derleyiciler, yorumlayıcılar, metin düzenleyiciler, sözdizim çözümleyiciler, ayrıştırıcılar (parsers) başta olmak üzere birçok yazılım bileşeninde de kullanılan modellerdir. Özdevinirler biçimsel dillerin sözdizimsel ve anlamsal çözümlemesinde kullanılan modeller olduğu için de özdevinirler ile biçimsel diller birbiriyle çok yakından ilişkili, birbirini tamamlayan konulardır.
Ders İçeriği
Aşağıda genel başlıkları ile dersin içeriği verilmiştir. Bu içerik teorik olarak ele alınacak. Ancak bu ders için geliştirilmiş Python kütüphaneleri çalışılacak ve uygulamalar yapılacak. Yazılım uygulamaları her hafta yapılmaya çalışılacak. Ders içeriğinde dönem içindeki akışa göre güncellemeler yapılabilir.
| HAFTA | İÇERİK | AÇIKLAMA |
| 1. | GİRİŞ | Ders hakkında bilgilendirme. |
| 2. | MATEMATİK TEMELLER | Ders için gerekli olan matematik alt yapısı verilecektir. |
| 3. | SONLU OTOMATLAR | Deterministik sonlu otomatların tanım ve özellikleri verilerek örnekleri incelenecektir. |
| 4. | DETERMİNİSTİK OLMAYAN SONLU OTOMATLAR | Deterministik olmayan sonlu otomatların tanım ve özellikleri verilerek örnekleri incelenecektir. |
| 5. | DÜZENLİ İFADELER | Düzen ifadeler tanımı ve özellikleri verilecek. Örnekler çözülecek. Programlama dillerindeki karşılıkları tartışılacak. |
| 6. | DÜZENSİZ DİLLER, PUMPING LEMMA | Pumping lemması ifade edilecek ve ispatlanacak. Buradan bir dilin hangi koşulda düzenli olamayacağı sorusu cevaplanacak. |
| 7. | BAĞLAMDAN BAĞIMSIZ GRAMERLER | Bağlam kavramı incelenecek. Bağlamdanb bağımsız gramerler ele alınacak. |
| 8. | ARASINAV | |
| 9. | PUSHDOWN OTOMATLAR | Pushdown otomatlar tanım ve özellikleri verilecek. Örnekler çözülecek. |
| 10. | BAĞLAMDAN BAĞIMSIZ OLMAYAN GRAMERLER | Bağlamdan bağımsız dilleri için pumping lemması ele alınacak. |
| 11. | TURING MAKİNELERİ | Turing makinelerinin tanım ve özellikleri verilecek. Örnekler çözülecek. |
| 12. | TURING MAKİNELERİ | Tring makinesi çeşitlerinden bahsedilecek. Bir algoritmanın tanımı yapılacak. Örnekler çözülecek. |
| 13. | KARAR VERİLEBİLİRLİK | Karar verilebilir diller incelenecek. |
| 14. | GENEL TEKRAR VE YAZILIM UYGULAMASI | Genel tekrar yapılıp tartışılacak. |
Derste yararlanılacak kaynaklar:
Introduction to the theory of computation Michael Sipser : Kitap, tüm dünyada bu alanda kullanılan en iyi kaynaklardan birisidir. Okunması kolay ve anlaşılır bir kaynak. İnternetten bulup indirebilirsiniz. Kitaptaki iki bölüm (ünite) bu ders kapsamında işlenmektedir.
Otomatlar, Biçimsel Diller ve Turing Makineleri : Ders kapsamındaki tüm konuları sistematik olarak işleyen ve çok sayıda çözümlü örnek barındıran güzel bir kaynak.
Özdevinirler Otomatlar Kuramı ve Biçimsel diller, Ünal Yarımağan; Bu alanda yazılmış ilk Türkçe eser. Oldukça zengin içeriğe sahip ancak biraz ağır. İlk iki kaynak bana göre daha uygun.
Video önerileri
Çok emek harcanarak hazırlanmış videoların yer aldığı bazı youtube kanallarını aşağıda listeledim. Mutlaka daha fazlası vardır. Konu anlatımı ve çözümü için oldukça fazla kaynak mevcut. Hepsine bakabilirsiniz.