🎯 Otomat Tasarımı Örnekleri

Bu modülde, çeşitli dil tanımlama problemleri için otomat tasarımı örneklerini inceleyeceğiz.

📊 Örnek 1: İkili Sayıların 3'e Bölünebilirliği

Problem

Σ = {0, 1} için, ikili sistemde 3'e bölünebilen sayıları kabul eden bir DFA tasarlayın.

Çözüm

Mantık

Bir sayının 3'e bölünebilmesi için, 3'e bölümünden kalan 0 olmalıdır. Her durumu mod 3 değerine göre tanımlayabiliriz:

  • q₀: Kalan = 0 (başlangıç ve kabul durumu)
  • q₁: Kalan = 1
  • q₂: Kalan = 2

🔍 Örnek 2: En Az Bir "a" İçeren Dizgiler

Problem

Σ = {a, b} için, en az bir "a" içeren dizgileri kabul eden DFA tasarlayın.

Çözüm

Mantık

  • q₀: Henüz "a" görülmedi (başlangıç durumu)
  • q₁: En az bir "a" görüldü (kabul durumu)

💻 Gerçek Dünya Uygulamaları

Derleyici Tasarımı

  • Lexical Analyzer: Anahtar kelimeleri, tanımlayıcıları ve operatörleri tanımak
  • Tokenization: Kaynak kodu tokenlara ayırma
  • Syntax Highlighting: Kod editörlerinde renklendirme

Metin İşleme

  • Pattern Matching: grep, sed, awk araçları
  • Search Engines: Metin arama algoritmaları
  • Spell Checkers: Yazım denetimi

Network Security

  • Intrusion Detection: Şüpheli trafik kalıplarını tespit
  • Firewall Rules: Paket filtreleme
  • Virus Scanning: Malware imza tarama

✅ Test Soruları (15 Soru)

Bilginizi ölçmek için aşağıdaki soruları cevaplayın.

Soru 1:

İkili sayılarda 3'e bölünebilirlik için kaç durum gerekir?

Soru 2:

"En az bir a içeren dizgiler" için kaç durum gerekir?

Soru 3:

Eşit sayıda a ve b içeren dizgiler için hangi otomat kullanılır?

Soru 4:

Subset construction algoritması ne yapar?

Soru 5:

Thompson yapılandırma algoritması ne için kullanılır?

Soru 6:

Lexical analyzer hangi otomatları kullanır?

Soru 7:

Pattern matching uygulamalarında hangi algoritmalar kullanılır?

Soru 8:

Firewall kurallarında hangi otomatlar kullanılır?

Soru 9:

İkili sayılarda 3'e bölünebilirlik DFA'sında kaç kabul durumu vardır?

Soru 10:

"En az bir a içeren dizgiler" DFA'sında başlangıç durumu kabul durumu mudur?

Soru 11:

NFA'dan DFA'ya dönüşümünde durum sayısı nasıl değişir?

Soru 12:

Düzenli ifadeden NFA oluşturmada kullanılan temel işlemler hangileridir?

Soru 13:

Spell checker uygulamalarında hangi otomatlar kullanılır?

Soru 14:

Intrusion detection sistemlerinde hangi özellikler aranır?

Soru 15:

Virus scanning'de kullanılan temel yaklaşım nedir?

💡 Flashcards (16 Kart)

Kavramları pekiştirmek için kartları tıklayın.

Modül 4 - Uygulama
3'e Bölünebilirlik DFA
İkili sayılar için mod 3 kalanlarına göre 3 durum: q₀(kalan=0), q₁(kalan=1), q₂(kalan=2). Kabul durumu q₀.
Modül 4 - Uygulama
En Az Bir "a" İçeren Dizgiler
2 durum: q₀(başlangıç, "a" görülmedi), q₁(kabul, "a" görüldü). "a" geçişi q₀→q₁, diğer geçişler aynı durumda kalır.
Modül 4 - Algoritma
Subset Construction
NFA'dan DFA'ya dönüşüm. NFA'nın durum kümelerinin tüm alt kümelerini yeni DFA'nın durumları olarak kullanır.
Modül 4 - Algoritma
Thompson Construction
Düzenli ifadeden NFA'ya dönüşüm. Birleştirme, alternatif ve Kleene yıldızı için ε-geçişli yapılar kullanır.
Modül 4 - Derleyici
Lexical Analyzer
Kaynak kodu tokenlara ayırır. Anahtar kelimeler, tanımlayıcılar, operatörler için DFA kullanır.
Modül 4 - Metin İşleme
Pattern Matching
grep, sed, awk gibi araçlar. KMP, Boyer-Moore algoritmaları otomat tabanlı çalışır.
Modül 4 - Güvenlik
Intrusion Detection
Şüpheli trafik kalıplarını algılar. Bilinen imza ve anormal davranış tespiti için otomatlar kullanılır.
Modül 4 - Güvenlik
Firewall
Paket filtreleme kuralları. DFA tabanlı pattern matching ile trafik kontrolü yapılır.
Modül 4 - Güvenlik
Virus Scanning
Malware imza tarama. Dosya içeriğinde belirli pattern'leri arar, DFA tabanlı algoritmalar kullanır.
Modül 4 - Arama
Search Engines
Metin arama algoritmaları. Inverted index ve otomat tabanlı pattern matching kullanır.
Modül 4 - Yazım
Spell Checker
Yazım denetimi. Trie yapıları ve DFA ile kelime doğrulama ve öneri üretme yapılır.
Modül 4 - Ağ
Network Protocol Analysis
Protokol doğrulama. TCP/IP paket yapısı için state machine'ler kullanılır.
Modül 4 - Donanım
Digital Circuit Design
Devre tasarımı. Finite state machine'ler ile sequential logic devreleri modellenir.
Modül 4 - Veri
Data Validation
Veri doğrulama. Email, telefon, tarih formatları için düzenli ifade tabanlı otomatlar kullanılır.
Modül 4 - NLP
Natural Language Processing
Tokenization ve POS tagging. Kelime ve cümle yapısı analizi için otomatlar kullanılır.
Modül 4 - Eşleştirme
KMP ve Boyer-Moore
Hızlı string matching algoritmaları. Otomat yapısına dayalı pattern arama teknikleri.
⬅️ Modül 3: Sonlu Otomatlar 🏠 Ana Sayfa