Özdevinirler (Otomatlar) Kuramı ve

Biçimsel Diller

Prof. Dr. Ahmet Ünal YARIMAĞAN

 "farkımız, kitaplarımızda"

Bu kitabımız nitelikli öğretim yapan 67 üniversitede ders kitabıdır...

 mürekkep kokulu kitaplar

ISBN: 978-605-9594-85-1, 352 sayfa, 3. Basım

Ocak 2023, (16,5x24 cm2), 80 gr. 1. hamur kağıt

Özdevinirler (Otomatlar) Kuramı ve Biçimsel Diller PDF     şimdi satın al

İÇİNDEKİLER

Önsöz

Terimlere Verilen Türkçe Karşılıklar

Kısaltmalar

1. Sonlu Özdevinirler

1.1.Sonlu Özdevinir (FA) Modeli

1.1.1. Deterministik Sonlu Özdevinir (DFA) Modeli

1.1.2. Deterministik Olmayan Sonlu Özdevinir (NFA) Modeli

1.1.3. Lambda (l) Geçişi

1.1.4.Deterministik ve Deterministik Olmayan Sonlu Özdevinir Modellerinin Denkliği

1.1.5. İki Yönlü Sonlu Özdevinir Modeli

1.2.Çıkış Üreten Özdevinirler

1.3.Sonlu Özdevinirlerin İndirgenmesi

1.3.1. Ardıl, Öncel, Denk ve Ayırdedilebilir Durum Tanımları

1.3.2. İndirgeme Yöntemi

1.3.2.1.Mealy Makinelerinin İndirgenmesi

1.3.2.2.Moore Makinelerinin İndirgenmesi

1.3.2.3.Deterministik Sonlu Özdevinirlerin (DFA) İndirgenmesi

1.4.Sorular (17 Soru)

2. Düzgün Kümeler ve Düzgün Deyimler

2.1. Düzgün Kümeler

2.2. Düzgün Deyimler

2.2.1.Düzgün Deyimlere Karşı Gelen Sonlu Özdevinirlerin Bulunması

2.2.2.Sonlu Özdevinirlerin Tanıdığı Kümelerin Birer Düzgün Deyim Olarak Bulunması

 Sorular 

3. Dilbilgisi ve Diller

3.1.Dilbilgisi ve Dilin Biçimsel Tanımı

3.2.Dilbilgisi ve Dillerin Sınıflandırılması

3.2.1Tür-0 Dilbilgisi ve Dil

3.2.2. Tür-1 Dilbilgisi ve Dil

3.2.3. Tür-2 Dilbilgisi ve Dil

3.2.4Tür-3 Dilbilgisi ve Dil

3.2.5. Sağ-Doğrusal ve Sol-Doğrusal Dilbilgisi

3.3.Düzgün Dil – Sonlu Özdevinir İlişkisi

3.3.1.Düzgün Dilbilgisinin Türettiği Dili Tanıyan Sonlu Özdevinirin Bulunması

3.3.2.Sonlu Özdevinirin Tanıdığı Dili Türeten Düzgün Dilbilgisinin Bulunması

3.4.Düzgün Dillerin Kimi Özellikleri

3.5. Sorular

4. Bağlamdan-Bağımsız Dilbilgisi ve Diller

4.1.Bağlamdan-Bağımsız Dilbilgisi

4.2.Türetme Ağacı

4.3.Dilbilgisinin Yalınlaştırılması

4.3.1. Özyineli Kural, Özyineli Değişken

4.3.2. Yok Edilebilir Değişken

4.3.3. Birim Türetme Kuralı

4.3.4. Yararsız Değişken, Simge ve Kurallar

4.4.Normal Biçimler

4.4.1. Chomsky Normal Biçimi

4.4.2. Greibach Normal Biçimi

4.5. Sorular

5. Yığıtlı Özdevinirler (Pushdown Automata)

5.1.Yığıtlı Özdevinirin Temel Modeli

5.2.Bağlamdan-Bağımsız Dilbilgisi (CFG)- Yığıtlı Özdevinir (PDA) İlişkisi

5.2.1. Verilen bir CFG’nin Eşdeğeri PDA’nın Bulunması

5.2.2. Verilen bir PDA’nın Eşdeğeri CFG’nin Bulunması

5.3. Sorular

6. Turing Makineleri

6.1.Turing Makinelerinin Temel Modeli

6.1.1. Soyut Makine Görünümü

6.1.2. Anlık Tanımlar (Instantaneous Descriptions)

6.1.3. Turing Makinesinin Tanıdığı Dil

6.2.Turing Makinesi Örnekleri

6.3.Turing Makinesi Modelinde Değişiklikler

6.4.Chomsky Sıradüzeni

6.5.  Sorular

7. Ayrıştırma İşlemleri (Parsing)

7.1.Ayrıştırma Türleri

7.1.1. Yukarıdan-Aşağıya Ayrıştırma (Top-down Parsing)

7.1.2. Aşağıdan-Yukarıya Ayrıştırma (Bottom-up Parsing)

7.2.Deterministik Ayrıştırma

7.2.1. LL(k) Dilbilgileri

7.2.2. LL(k) Ayrıştırma

7.2.2.1.LL(k) Ayrıştırmada Kullanılacak PDA Modeli

7.2.2.2.LL(k) Ayrıştırma Çizelgesinin Oluşturulması

7.2.3. LR(k) Dilbilgileri

7.2.4. LR(k) Ayrıştırma

7.2.4.1.LR(k) Ayrıştırmada Kullanılacak PDA Modeli

7.2.4.2.İşaretli Kurallar

7.2.4.3.LR(1) Ayrıştırıcı Geçiş Çizeneğinin Oluşturulması

7.2.4.4.LR(1) Ayrıştırma Çizelgesinin Oluşturulması

7.2.4.5.LR(1) Ayrıştırma Sürecinin Yürütülmesi

7.3. Sorular

Soruların Yanıtları

Bölüm 1

Bölüm 2

Bölüm 3

Bölüm 4

Bölüm 5

Bölüm 6

Bölüm 7

Kaynakça

Dizin

Önsöz.

Bu kitabın konusu olan “özdevinirler (otomatlar) kuramı ve biçimsel diller” bilgisayar bilimleri ve mühendisliğinin kuramsal temelleri alanının en önemli konularından birisidir. Bu nedenle bilgisayar bilimleri ve bilgisayar mühendisliği alanında eğitim veren lisans programaları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.

Kitabın özdevinirler kuramı ve biçimsel diller konusundaki ilk Türkçe kitap olduğunu sanıyorum. Kitabın ana kaynağı, Hacettepe Üniversitesi Bilgisayar Mühendisliği Bölümünde okutulmakta olan "Özdevinirler Kuramı ve Biçimsel Diller" dersinin notlarıdır. Bu nedenle kitabın içeriği özellikle bilgisayar mühendisliği bölümlerinde lisans düzeyinde okutulacak bir ders için uygundur. Kitaptaki konular, haftalık süresi 3 saat olan bir derste işlenebilecek biçimde düzenlenmiştir.

Özdevinirler kuramı ve biçimsel diller dersini Hacettepe Üniversitesi Bilgisayar Mühendisliği Bölümünde 12 yıldan beri vermekte olduğum için, bu konuda küçümsenmeyecek bir soru bankasına sahibim. Bu soruların büyük bir kısmı kitapta yer almaktadır. Kitabın en özgün yanının da soru ve yanıtlar olduğunu düşünüyorum. Soruların her biri en az bir kez sınavda sorulmuş ve ölçme açısından başarılı olduğu görülmüştür. Kitapta yer alan tüm soruların yanıtları verilmiştir. Ancak kitabın sayfa sayısının çok artmaması için, yanıtlar kısa tutulmaya çalışılmış, bazı sorular için ise sonucun verilmesi ile yetinilmiştir. Diğer taraftan bazı soruların birden çok geçerli yanıtının olabileceği; yanıtı tek olan soruların birçoğu için de birden çok çözüm yolunun olabileceği bir gerçektir. Bu nedenle kitapta yer alan çözümlerin örnek çözümler olduğu; bazı sorular için verilen çözüm dışında başka çözüm ya da çözümlerin de olabileceği unutulmamalıdır. ~ Prof. Dr. Ünal Yarımağan

Kitaplarımızın tüm listesi için buraya tıklayınız.

Papatya Bilim Üniversite Ders Kitapları, Akademik Kitaplar, Bilimsel Kitaplar