📚 Temel Tanımlar ve Notasyonlar
1. Alfabe (Σ)
Σ = Sonlu ve boş olmayan sembol kümesi
Örnekler:
Σ = {0, 1} → İkili alfabe
Σ = {a, b, c} → Üç harfli alfabe
Σ = {0, 1, 2, ..., 9} → Onlu alfabe
Σ = {0, 1} → İkili alfabe
Σ = {a, b, c} → Üç harfli alfabe
Σ = {0, 1, 2, ..., 9} → Onlu alfabe
2. Kelime (String/Word)
w = Alfabe sembollerinin sonlu dizisi
|w| = Kelimenin uzunluğu
ε = Boş kelime (uzunluğu 0)
|w| = Kelimenin uzunluğu
ε = Boş kelime (uzunluğu 0)
Örnekler:
w = "010" → |w| = 3
w = "abc" → |w| = 3
w = ε → |w| = 0
w = "010" → |w| = 3
w = "abc" → |w| = 3
w = ε → |w| = 0
3. Dil (Language)
L ⊆ Σ* (Σ üzerindeki kelimelerin bir alt kümesi)
Σ* = Σ alfabesi üzerinden oluşturulabilecek tüm kelimeler
Σ* = Σ alfabesi üzerinden oluşturulabilecek tüm kelimeler
Örnekler:
Σ = {0, 1} için Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, ...}
L = {w | w, 0 ile başlar} = {0, 00, 01, 000, 001, ...}
L = {0ⁿ1ⁿ | n ≥ 0} = {ε, 01, 0011, 000111, ...}
Σ = {0, 1} için Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, ...}
L = {w | w, 0 ile başlar} = {0, 00, 01, 000, 001, ...}
L = {0ⁿ1ⁿ | n ≥ 0} = {ε, 01, 0011, 000111, ...}
🔄 Düzenli İfade Operatörleri
| Operatör | Notasyon | Açıklama | Örnek |
|---|---|---|---|
| Birleşim | r + s veya r | s | r veya s dillerinden biri | a+b = {a, b} |
| Birleştirme | rs veya r·s | r ardından s | ab = {ab} |
| Kleene Yıldızı | r* | r'nin 0 veya daha fazla tekrarı | a* = {ε, a, aa, aaa, ...} |
| Pozitif Kapama | r+ | r'nin 1 veya daha fazla tekrarı | a+ = {a, aa, aaa, ...} |
| İsteğe Bağlı | r? | r veya ε | a? = {ε, a} |
| Parantez | (r) | Öncelik belirleme | (a+b)* ≠ a+b* |
Operatör Önceliği (Yüksekten Düşüğe)
1. Parantez: ( )
2. Kleene Yıldızı: *
3. Birleştirme: ·
4. Birleşim: +
2. Kleene Yıldızı: *
3. Birleştirme: ·
4. Birleşim: +
Örnek:
ab* = a(b*) ≠ (ab)*
a+bc = a+(bc) = (a)+(bc)
(a+b)* = Hem a hem b içeren tüm kelimeler
ab* = a(b*) ≠ (ab)*
a+bc = a+(bc) = (a)+(bc)
(a+b)* = Hem a hem b içeren tüm kelimeler
🤖 DFA (Deterministik Sonlu Otomat)
DFA Tanımı: M = (Q, Σ, δ, q₀, F)
Q: Sonlu durum kümesi
Σ: Giriş alfabesi
δ: Geçiş fonksiyonu (Q × Σ → Q)
q₀: Başlangıç durumu (q₀ ∈ Q)
F: Kabul durumları kümesi (F ⊆ Q)
DFA Özellikleri
✓ Her durum ve sembol çifti için TAM BİR geçiş vardır
✓ Herbir durum ve sembol için sadece BİR geçiş vardır
✓ ε-geçişi yoktur
✓ Deterministik: Aynı giriş için her zaman aynı yolu izler
✓ Herbir durum ve sembol için sadece BİR geçiş vardır
✓ ε-geçişi yoktur
✓ Deterministik: Aynı giriş için her zaman aynı yolu izler
DFA Örnek
Σ = {0, 1} üzerinde çift sayıda 1 içeren kelimeler:
Q = {q₀, q₁}
Σ = {0, 1}
q₀ = başlangıç (çift durum)
F = {q₀}
δ:
δ(q₀, 0) = q₀
δ(q₀, 1) = q₁
δ(q₁, 0) = q₁
δ(q₁, 1) = q₀
Q = {q₀, q₁}
Σ = {0, 1}
q₀ = başlangıç (çift durum)
F = {q₀}
δ:
δ(q₀, 0) = q₀
δ(q₀, 1) = q₁
δ(q₁, 0) = q₁
δ(q₁, 1) = q₀
🔀 NFA (Nondeterministik Sonlu Otomat)
NFA Tanımı: M = (Q, Σ, δ, q₀, F)
Q: Sonlu durum kümesi
Σ: Giriş alfabesi
δ: Geçiş fonksiyonu (Q × (Σ ∪ {ε}) → 2^Q)
q₀: Başlangıç durumu
F: Kabul durumları kümesi
NFA Özellikleri
✓ Bir durum ve sembol için 0, 1 veya daha fazla geçiş olabilir
✓ ε-geçişi olabilir (giriş okumadan durum değişimi)
✓ Nondeterministik: Birden fazla yol seçeneği olabilir
✓ Kelime kabul edilir ⟺ En az bir yol kabul durumunda biter
✓ ε-geçişi olabilir (giriş okumadan durum değişimi)
✓ Nondeterministik: Birden fazla yol seçeneği olabilir
✓ Kelime kabul edilir ⟺ En az bir yol kabul durumunda biter
| Özellik | DFA | NFA |
|---|---|---|
| Geçiş Sayısı | Her (q, a) için tam 1 tane | Her (q, a) için 0+ tane |
| ε-geçiş | Yok | Olabilir |
| Güç | Düzenli dilleri tanır | Düzenli dilleri tanır |
| Tasarım | Daha karmaşık | Daha kolay |
| Durum Sayısı | Daha fazla gerekebilir | Daha az olabilir |
🔒 Düzenli Dillerin Kapama Özellikleri
Düzenli Diller Kapalıdır:
✅ Birleşim: L₁ ∪ L₂
✅ Kesişim: L₁ ∩ L₂
✅ Tümleyen: L̄ (Σ* - L)
✅ Birleştirme: L₁L₂
✅ Kleene Yıldızı: L*
✅ Ters: L^R (kelimelerin tersi)
✅ Fark: L₁ - L₂
✅ Kesişim: L₁ ∩ L₂
✅ Tümleyen: L̄ (Σ* - L)
✅ Birleştirme: L₁L₂
✅ Kleene Yıldızı: L*
✅ Ters: L^R (kelimelerin tersi)
✅ Fark: L₁ - L₂
İspat Teknikleri
Bir dilin düzenli olduğunu göstermek için:
1. DFA/NFA tasarlayın
2. Düzenli ifade yazın
3. Kapama özelliklerini kullanın
Bir dilin düzenli olmadığını göstermek için:
1. Pompalama lemması kullanın
2. Kapalı olmadığı işlemi gösterin
1. DFA/NFA tasarlayın
2. Düzenli ifade yazın
3. Kapama özelliklerini kullanın
Bir dilin düzenli olmadığını göstermek için:
1. Pompalama lemması kullanın
2. Kapalı olmadığı işlemi gösterin
🔄 Dönüşüm İşlemleri
1. NFA → DFA (Alt Küme İnşası)
1. NFA'nın durumlarının tüm alt kümelerini oluştur (2^n durum)
2. Başlangıç: {q₀} ve ε-kapaması
3. Her alt küme için geçişleri hesapla
4. Kabul durumları: F'den en az bir durum içerenler
2. Başlangıç: {q₀} ve ε-kapaması
3. Her alt küme için geçişleri hesapla
4. Kabul durumları: F'den en az bir durum içerenler
2. Düzenli İfade → NFA (Thompson İnşası)
• Temel: Tek sembol için 2 durumlu NFA
• Birleşim (r+s): Paralel yollar, ε-geçişlerle
• Birleştirme (rs): Seri bağlantı
• Kleene (*): Döngü, ε-geçişlerle
• Birleşim (r+s): Paralel yollar, ε-geçişlerle
• Birleştirme (rs): Seri bağlantı
• Kleene (*): Döngü, ε-geçişlerle
3. DFA → Düzenli İfade (Arden Teoremi)
Her durum için denklem yaz:
Q_i = aQ_j + bQ_k + ... + (ε eğer i kabul durumuysa)
Arden Teoremi:
R = Q + RP → R = QP*
Q_i = aQ_j + bQ_k + ... + (ε eğer i kabul durumuysa)
Arden Teoremi:
R = Q + RP → R = QP*
🔍 Pompalama Lemması
Pompalama Lemması (Düzenli Diller için)
L düzenli bir dil ise, bir p (pompalama uzunluğu) sayısı vardır ki:
Tüm w ∈ L için |w| ≥ p ise, w = xyz şeklinde yazılabilir ve:
1. |y| > 0 (y boş değildir)
2. |xy| ≤ p
3. Tüm i ≥ 0 için xy^iz ∈ L
Pompalama Lemması Kullanımı
L = {0ⁿ1ⁿ | n ≥ 0} dilinin düzenli olmadığını göster:
1. Dilin düzenli olduğunu varsay
2. p pompalama uzunluğu olsun
3. w = 0^p 1^p seç (|w| = 2p ≥ p)
4. w = xyz olarak ayır
5. |xy| ≤ p olduğundan y sadece 0'lardan oluşur
6. xy²z = 0^(p+|y|) 1^p ∉ L (çelişki!)
7. L düzenli değildir ✓
1. Dilin düzenli olduğunu varsay
2. p pompalama uzunluğu olsun
3. w = 0^p 1^p seç (|w| = 2p ≥ p)
4. w = xyz olarak ayır
5. |xy| ≤ p olduğundan y sadece 0'lardan oluşur
6. xy²z = 0^(p+|y|) 1^p ∉ L (çelişki!)
7. L düzenli değildir ✓
⚡ Hızlı Referans Tablosu
| Sembol | Anlamı | Örnek |
|---|---|---|
| Σ | Alfabe | Σ = {0, 1} |
| Σ* | Tüm kelimelerin kümesi | {ε, 0, 1, 00, 01, ...} |
| ε | Boş kelime | |ε| = 0 |
| |w| | Kelimenin uzunluğu | |abc| = 3 |
| w^R | Kelimenin tersi | (abc)^R = cba |
| L₁ ∪ L₂ | Birleşim | {a,b} ∪ {b,c} = {a,b,c} |
| L₁ ∩ L₂ | Kesişim | {a,b} ∩ {b,c} = {b} |
| L̄ | Tümleyen | L̄ = Σ* - L |
| L₁L₂ | Birleştirme | {a,b}{c} = {ac, bc} |
| L* | Kleene yıldızı | {a}* = {ε,a,aa,aaa,...} |
| δ | Geçiş fonksiyonu | δ(q₀, a) = q₁ |
| q₀ | Başlangıç durumu | Otomat q₀'dan başlar |
| F | Kabul durumları | F ⊆ Q |
| ⊆ | Alt küme | F ⊆ Q |
| ∈ | Eleman | q₀ ∈ Q |
💡 Önemli Hatırlatmalar
✅ DFA ve NFA'nın gücü eşittir (her NFA'ya eşdeğer bir DFA vardır)
✅ Düzenli ifadeler, DFA ve NFA eşdeğerdir
✅ Her düzenli dil bir DFA ile tanınabilir
✅ Düzenli diller birleşim, kesişim, tümleyen altında kapalıdır
✅ Pompalama lemması düzensizlik göstermek için kullanılır
✅ {0ⁿ1ⁿ} düzenli değildir (klasik örnek)