🤖 Sonlu Otomatların Tanımı
Sonlu Otomat: Sonlu sayıda durum, giriş alfabesi ve durum geçişi kurallarına sahip matematiksel bir soyutlamadır.
📋 Biçimsel Tanım
M = (Q, Σ, δ, s, F)
- Q: Durumların sonlu kümesi
- Σ: Giriş alfabesi
- δ: Geçiş fonksiyonu
- s: Başlangıç durumu
- F: Kabul durumları
🔄 DFA ve NFA
Deterministik Sonlu Otomat (DFA)
Her durum ve her giriş sembolü için tam olarak bir geçiş tanımlanır.
Nondeterministik Sonlu Otomat (NFA)
Bir durumdan aynı giriş sembolü için birden fazla geçiş olabilir ve ε-geçişler yapabilir.
📝 Bilgi Testi - Modül 3
1. DFA nedir?
Doğru Cevap: Deterministik Sonlu Otomat
2. NFA'nın DFA'dan temel farkı nedir?
Doğru Cevap: Aynı durum/sembol için birden fazla geçiş yapabilir
3. Q bileşeni neyi temsil eder?
Doğru Cevap: Durumların sonlu kümesini
4. δ fonksiyonu nasıl gösterilir?
Doğru Cevap: δ: Q × Σ → Q
5. NFA'dan DFA'ya dönüşümde hangi yöntem kullanılır?
Doğru Cevap: Alt küme yapısı metodu
6. Kabul durumları nasıl gösterilir?
Doğru Cevap: Çift çember ile
7. F bileşeni neyi temsil eder?
Doğru Cevap: Kabul durumlarını
8. Bir kelime ne zaman kabul edilir?
Doğru Cevap: Başlangıçtan kabul durumunda bitirse
9. ε-geçişler hangi otomatta kullanılır?
Doğru Cevap: ε-NFA'da
10. Durum minimizasyonunun amacı nedir?
Doğru Cevap: Eşdeğer durumları birleştirmek
Toplam: 10
💡 Flashcard'lar - Modül 3
Modül 3
DFA
Deterministik Sonlu Otomat - her durum/sembol için tam bir geçiş
Modül 3
NFA
Nondeterministik Sonlu Otomat - aynı durum/sembol için birden fazla geçiş
Modül 3
Q
Durumların sonlu kümesi. Örnek: Q = {q0, q1, q2}
Modül 3
Σ
Giriş alfabesi - sembollerden oluşan sonlu küme
Modül 3
δ
Geçiş fonksiyonu: δ: Q × Σ → Q
Modül 3
F
Kabul durumları - Q'nun alt kümesi
Modül 3
Geçiş Diyagramı
Durumlar dairelerle, geçişler okla, kabul durumları çift çemberle
Modül 3
Geçiş Tablosu
Satırlar durumlar, sütunlar semboller, hücreler hedef durumlar
Modül 3
ε-Geçişler
ε-NFA'da girdi okumadan durum değişikliği
Modül 3
Alt Küme Metodu
NFA'dan DFA'ya dönüşüm yöntemi
Modül 3
Tasarım Adımları
Dili tanımla, alfabeyi belirle, durumları tanımla, geçişleri çiz
Modül 3
Kelime Kabul
Başlangıçtan başlayıp kabul durumunda bitirmek
Modül 3
Durum Minimizasyonu
Eşdeğer durumları birleştirerek optimal DFA oluşturma
Modül 3
Tamamlama
Eksik geçişleri çöp durum (sink state) ile tamamlama
Modül 3
Güç Denkliği
DFA ve NFA tanıma güçleri eşittir