BİÇİMSEL DİLLER VE OTOMATA TEORİSİ – Dr. İnan Ünal | Matematik

Ders hakkında;

Ö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:

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.

Sorularınızı ve önerilerini inanhoca@gmail.com adresine yollayabilirsiniz.

	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.
	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.
	Ö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.