Pratik Problemler

Çözüm:

Durum Kümesi: Q = {q₀, q₁, q₂}

Başlangıç: q₀

Kabul Durumları: F = {q₁}

Geçiş Fonksiyonu:

• δ(q₀, 0) = q₂ (reddedildi, 0 ile başladı)
• δ(q₀, 1) = q₁ (kabul, 1 ile başladı)
• δ(q₁, 0) = q₁ (kabul durumunda kal)
• δ(q₁, 1) = q₁ (kabul durumunda kal)
• δ(q₂, 0) = q₂ (red durumunda kal)
• δ(q₂, 1) = q₂ (red durumunda kal)

✅ 3 durumlu DFA: İlk sembolü kontrol et ve sonuç durumda kal

Çözüm:

Durum Kümesi: Q = {q₀, q₁}

• q₀ = çift sayıda 'a' (kabul)

• q₁ = tek sayıda 'a' (red)

Geçiş Fonksiyonu:

• δ(q₀, a) = q₁ (çift → tek)
• δ(q₀, b) = q₀ (çift → çift)
• δ(q₁, a) = q₀ (tek → çift)
• δ(q₁, b) = q₁ (tek → tek)

✅ 2 durumlu DFA: 'a' sayısının paritesini tut

Çözüm:

Fikir: Her durumu "mod 3" değerine göre tanımla

Durum Kümesi: Q = {q₀, q₁, q₂}

• q₀: sayı ≡ 0 (mod 3) - KABUL

• q₁: sayı ≡ 1 (mod 3)

• q₂: sayı ≡ 2 (mod 3)

Geçiş Fonksiyonu:

Yeni bit eklendiğinde: yeni_değer = (eski_değer × 2 + bit) mod 3

• δ(q₀, 0) = q₀ (0×2+0 = 0 mod 3 = 0)
• δ(q₀, 1) = q₁ (0×2+1 = 1 mod 3 = 1)
• δ(q₁, 0) = q₂ (1×2+0 = 2 mod 3 = 2)
• δ(q₁, 1) = q₀ (1×2+1 = 3 mod 3 = 0)
• δ(q₂, 0) = q₁ (2×2+0 = 4 mod 3 = 1)
• δ(q₂, 1) = q₂ (2×2+1 = 5 mod 3 = 2)

✅ 3 durumlu DFA: Mod 3 değerini takip et

Çözüm:

Analiz:

• (a+b)* → a ve b'lerden oluşan herhangi bir kelime (ε dahil)
• abb → 'abb' ile bitme zorunluluğu

Dil: L = {w | w, 'abb' ile biten kelimelerdir}

Örnekler:

• ✅ abb
• ✅ aabb
• ✅ babbabb
• ✅ aababb
• ❌ ab (abb ile bitmiyor)
• ❌ abba (abb ile bitmiyor)

✅ 'abb' ile biten tüm kelimeler

Çözüm:

Yaklaşım: Hem 0 hem 1 içermeli

Yöntem 1: (0+1)*0(0+1)*1(0+1)* + (0+1)*1(0+1)*0(0+1)*

• Önce 0, sonra 1 VEYA önce 1, sonra 0

Yöntem 2 (Basit):

0*(10*)*1(0+1)* + 1*(01*)*0(0+1)*

Test:

• ✅ 01 → kabul
• ✅ 10 → kabul
• ✅ 001 → kabul
• ✅ 1100 → kabul
• ❌ 000 → red (1 yok)
• ❌ 111 → red (0 yok)

✅ Birden fazla doğru cevap var

Çözüm:

Sol Taraf: (a*b*)*

• a*b* → önce a'lar, sonra b'ler (aaabbb gibi)
• (a*b*)* → bunların tekrarı
• Üretebilir: ε, a, b, aa, ab, ba, bb, aab, abb, ...

Sağ Taraf: (a+b)*

• a ve b'lerin herhangi bir sırada tekrarı
• Üretebilir: ε, a, b, aa, ab, ba, bb, aab, abb, ...

Karşılaştırma:

Her iki ifade de Σ = {a, b} üzerindeki TÜM kelimeleri üretir.

Örnek: "aba" kelimesi:

• Sol: (a*b*)* → (a)()(b)()(a) ✅
• Sağ: (a+b)* → a·b·a ✅

✅ DOĞRU: (a*b*)* = (a+b)*

Çözüm:

NFA Avantajı: Nondeterminizm sayesinde daha basit

Durum Kümesi: Q = {q₀, q₁, q₂, q₃, q₄, q₅}

Strateji: İki paralel yol

• Yol 1: "ab" arıyor (q₀ → q₁ → q₂)
• Yol 2: "ba" arıyor (q₀ → q₃ → q₄)

Geçişler:

• δ(q₀, a) = {q₀, q₁} (devam et veya "ab" yoluna gir)
• δ(q₀, b) = {q₀, q₃} (devam et veya "ba" yoluna gir)
• δ(q₁, b) = {q₂} ("ab" bulundu!)
• δ(q₂, a) = {q₂} (kabul durumunda kal)
• δ(q₂, b) = {q₂}
• δ(q₃, a) = {q₄} ("ba" bulundu!)
• δ(q₄, a) = {q₄} (kabul durumunda kal)
• δ(q₄, b) = {q₄}

Kabul: F = {q₂, q₄}

✅ NFA ile DFA'dan daha az durumla çözülebilir

Çözüm (Thompson İnşası):

Adım 1: a ve b için temel NFA'lar

Adım 2: a+b (birleşim) için ε-geçişlerle birleştir

Adım 3: (a+b)* için döngü ekle (ε-geçişle)

Adım 4: ...c ekle

Sonuç NFA:

• q₀ --ε--> q₁ (a veya b döngüsüne)
• q₁ --a--> q₂ --ε--> q₁ (döngü)
• q₁ --b--> q₃ --ε--> q₁ (döngü)
• q₁ --ε--> q₄ (döngüden çık)
• q₄ --c--> q₅ (kabul durumu)

✅ Thompson metoduyla sistematik inşa

Çözüm:

Varsayım: L düzenli olsun.

Adım 1: p (pompalama uzunluğu) var olsun.

Adım 2: w = aᵖbᵖ seçelim (|w| = 2p ≥ p)

Adım 3: Pompalama lemmasına göre w = xyz şeklinde ayrılabilir:

• |y| > 0
• |xy| ≤ p
• ∀i ≥ 0, xy^iz ∈ L

Adım 4: |xy| ≤ p olduğundan, xy sadece a'lardan oluşur.

Dolayısıyla y = aᵏ (k > 0)

Adım 5: i = 2 için xy²z'yi kontrol edelim:

xy²z = aᵖ⁺ᵏbᵖ (a sayısı p+k, b sayısı p)

p+k > p olduğundan, xy²z ∉ L

Çelişki! Dolayısıyla L düzenli değildir.

✅ L = {aⁿbⁿ} düzenli DEĞİLDİR

Çözüm:

Örnekler: aba, abba, aa, ε (palindromlar)

Varsayım: L düzenli olsun.

Kelime seçimi: w = aᵖbaᵖ (|w| = 2p+1 ≥ p)

Bu kelime palindromdur: tersinden okunduğunda aᵖbaᵖ = aᵖbaᵖ

Pompalama: w = xyz ve |xy| ≤ p

Yine, xy sadece ilk a'lardan oluşur: y = aᵏ (k > 0)

i = 2: xy²z = aᵖ⁺ᵏbaᵖ

Bu palindrom mu? Tersinden: aᵖbaᵖ⁺ᵏ

aᵖ⁺ᵏbaᵖ ≠ aᵖbaᵖ⁺ᵏ → Palindrom değil!

✅ Palindromlar düzenli değildir

Çözüm (Tablo Doldurma Yöntemi):

Adım 1: Kabul ve red durumlarını ayır

• Grup 1: {q₀, q₁} (red)

• Grup 2: {q₂, q₃} (kabul)

Adım 2: Her grup içinde geçişleri kontrol et

Eğer aynı gruptaki iki durum farklı gruplara geçiyorsa, ayır.

Adım 3: Eşdeğer durumları birleştir

Eğer q₂ ve q₃ her sembol için aynı gruplara geçiyorsa birleştir.

✅ Minimum DFA: Eşdeğer durumlar birleştirilir

Çözüm (Çarpım İnşası):

Verilen: M₁ = (Q₁, Σ, δ₁, q₁, F₁) ve M₂ = (Q₂, Σ, δ₂, q₂, F₂)

İnşa edelim: M = (Q, Σ, δ, q₀, F)

• Q = Q₁ × Q₂ (durum çiftleri)
• q₀ = (q₁, q₂)
• F = F₁ × F₂ (her iki otomatada da kabul)
• δ((p,q), a) = (δ₁(p,a), δ₂(q,a))

Neden çalışır?

M, w kelimesini kabul eder ⟺

Hem M₁ hem M₂ w'yi kabul eder ⟺

w ∈ L₁ ∩ L₂

✅ Düzenli diller kesişim altında kapalıdır