BİÇİMSEL DİLLERE VE AUTOMATA TEORİSİNE GİRİŞ

AMAÇ

Bu ders, Otomata teorisindeki kavramları tanıtmayı amaçlamaktadır. Farklı biçimsel dil sınıflarını, aralarındaki ilişkileri ve farklılıkları belirleme konularına dayanmaktadır. Öğrencilerden belirli amaçlara yönelik teorik makineler tasarlamaları ve bu makinelerin özelliklerini kanıtlamaları/çürütmeleri beklenir.

İÇERİK

Bu ders; Kurs Bilgisi, Sonlu Durum Otomatlarına Giriş,Deterministik ve Deterministik Olmayan Sonlu Durum Otomataları,Deterministik ve deterministik olmayan Otomatların denkliği,Düzenli İfade ,Düzenli ifade için Cebirsel Kanunlar,Düzenli Diller için Pompalama Lemması ve sonlu durum otomatlarının minimizasyonu,Bağlamdan Bağımsız Gramerler ,Bağlamdan Bağımsız Diller,Ayrıştırma Ağaçları ve Dilbilgisinin Belirsizliği,Pushdown Automata ,Chomsky Normal Formu,Bağlamdan Bağımsız diller için Lemma Pompalama,Turing makineleri,Turing makineları ile basit matematiksel işlemler; konularını içermektedir.

1. 1

   Identify different classes of languages and design automaton to accept that language

   Öğretim yöntemi: Öğretme – öğrenme yöntem ve stratejileri, öğrencilerin kendi kendine çalışma, yaşam boyu öğrenme, gözlem yapma, başkasına öğretme, sunma, eleştirel düşünme, takım çalışması, bilişimden etkin yararlanma gibi becerilerini arttıracak şekilde seçilmektedir. Ayrıca, öğretim tarzının farklı kabiliyetleri olan öğrencileri destekleyecek biçimde olmasına dikkat edilir. Programında kullanılan eğitim-öğretim metotları aşağıdaki listede verilmiştir **: Eğitim - Öğretim Yöntemleri *, Tartışma Yöntemi, Tartışma Yöntemi, Örnek Olay Yöntemi, Bireysel Çalışma Yöntemi, Probleme Dayalı Öğrenme Modeli, Kavram Haritası Tekniği, Proje Temelli Öğrenme Modeli, Deneyimle Öğrenme Modeli · Değerlendirme: Klasik Yazılı Sınav, Kısa Sınav

2. 2

   Prove or disprove if the given language is regular, proving equivalence of different automata

   Öğretim yöntemi: Öğretme – öğrenme yöntem ve stratejileri, öğrencilerin kendi kendine çalışma, yaşam boyu öğrenme, gözlem yapma, başkasına öğretme, sunma, eleştirel düşünme, takım çalışması, bilişimden etkin yararlanma gibi becerilerini arttıracak şekilde seçilmektedir. Ayrıca, öğretim tarzının farklı kabiliyetleri olan öğrencileri destekleyecek biçimde olmasına dikkat edilir. Programında kullanılan eğitim-öğretim metotları aşağıdaki listede verilmiştir **: Eğitim - Öğretim Yöntemleri *, Tartışma Yöntemi, Tartışma Yöntemi, Örnek Olay Yöntemi, Bireysel Çalışma Yöntemi, Probleme Dayalı Öğrenme Modeli, Kavram Haritası Tekniği, Proje Temelli Öğrenme Modeli, Deneyimle Öğrenme Modeli · Değerlendirme: Klasik Yazılı Sınav, Kısa Sınav

3. 3

   Represent a given language by a context-free grammar, removing ambiguity, and simplification of a given grammar.

   Öğretim yöntemi: Öğretme – öğrenme yöntem ve stratejileri, öğrencilerin kendi kendine çalışma, yaşam boyu öğrenme, gözlem yapma, başkasına öğretme, sunma, eleştirel düşünme, takım çalışması, bilişimden etkin yararlanma gibi becerilerini arttıracak şekilde seçilmektedir. Ayrıca, öğretim tarzının farklı kabiliyetleri olan öğrencileri destekleyecek biçimde olmasına dikkat edilir. Programında kullanılan eğitim-öğretim metotları aşağıdaki listede verilmiştir **: Eğitim - Öğretim Yöntemleri *, Tartışma Yöntemi, Tartışma Yöntemi, Örnek Olay Yöntemi, Bireysel Çalışma Yöntemi, Probleme Dayalı Öğrenme Modeli, Kavram Haritası Tekniği, Proje Temelli Öğrenme Modeli, Deneyimle Öğrenme Modeli · Değerlendirme: Klasik Yazılı Sınav, Kısa Sınav

4. 4

   Desing a Turing machine for a certain purpose.

   Öğretim yöntemi: Öğretme – öğrenme yöntem ve stratejileri, öğrencilerin kendi kendine çalışma, yaşam boyu öğrenme, gözlem yapma, başkasına öğretme, sunma, eleştirel düşünme, takım çalışması, bilişimden etkin yararlanma gibi becerilerini arttıracak şekilde seçilmektedir. Ayrıca, öğretim tarzının farklı kabiliyetleri olan öğrencileri destekleyecek biçimde olmasına dikkat edilir. Programında kullanılan eğitim-öğretim metotları aşağıdaki listede verilmiştir **: Eğitim - Öğretim Yöntemleri *, Tartışma Yöntemi, Tartışma Yöntemi, Örnek Olay Yöntemi, Bireysel Çalışma Yöntemi, Soru - Cevap Tekniği, Probleme Dayalı Öğrenme Modeli, Kavram Haritası Tekniği, Proje Temelli Öğrenme Modeli, Deneyimle Öğrenme Modeli · Değerlendirme: Klasik Yazılı Sınav, Kısa Sınav

HAFTALIK PLAN

1. HAFTA 1

   Kurs Bilgisi, Sonlu Durum Otomatlarına Giriş

   Ön hazırlık: Kitap Bölüm 1

2. HAFTA 2

   Deterministik ve Deterministik Olmayan Sonlu Durum Otomataları

   Ön hazırlık: Kitap Bölüm 2.1-2.3

3. HAFTA 3

   Deterministik ve deterministik olmayan Otomatların denkliği

   Ön hazırlık: Kitap Bölüm 2.3

4. HAFTA 4

   Düzenli İfade

   Ön hazırlık: Kitap Bölüm 3

5. HAFTA 5

   Düzenli ifade için Cebirsel Kanunlar

   Ön hazırlık: Kitap Bölüm 4.2

6. HAFTA 6

   Düzenli Diller için Pompalama Lemması ve sonlu durum otomatlarının minimizasyonu

   Ön hazırlık: Kitap Bölüm 4.1

7. HAFTA 7

   Bağlamdan Bağımsız Gramerler

   Ön hazırlık: Kitap Bölüm 5.1

8. HAFTA 8

   Bağlamdan Bağımsız Diller

   Ön hazırlık: Kitap Bölüm 5.1, 5.4

9. HAFTA 9

   Ayrıştırma Ağaçları ve Dilbilgisinin Belirsizliği

   Ön hazırlık: Kitap Bölüm 5.4

10. HAFTA 10

    Pushdown Automata

    Ön hazırlık: Kitap Bölüm 6

11. HAFTA 11

    Chomsky Normal Formu

    Ön hazırlık: Kitap Bölüm 7.1

12. HAFTA 12

    Bağlamdan Bağımsız diller için Lemma Pompalama

    Ön hazırlık: Kitap Bölüm 7.2

13. HAFTA 13

    Turing makineleri

    Ön hazırlık: Kitap Bölüm 8.1

14. HAFTA 14

    Turing makineları ile basit matematiksel işlemler

    Ön hazırlık: Kitap Bölüm 8.1,8.2

DEĞERLENDİRME

• Ara Sınavın Başarıya Oranı30%
• Genel Sınavın Başarıya Oranı70%

İŞ YÜKÜ

KAYNAKLAR

• Lecture notes will be supplied by instructor but following textbooks could be used as supplementary materials. 1. J. Hopcroft, R. Motwani, and J. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd edition, 2007, Pearson/Addison-Wesley, 2. Theory of Automata By C.J. Martin

ÖĞRETİM ELEMANLARI

• Assist.Prof. Cihan Bilge GÜRBÜZKOORDİNATÖR
• Assist.Prof. Cihan Bilge GÜRBÜZ