DFA İndirgenmesi (DFA Minimization)

DFA (1)

Bu yazımda bilgisayar bilimlerinin temel derslerinden olan Biçimsel Diller ve Soyut Makineler dersi için önemli bir konu olan DFA makinesinin optimizasyonunu anlatacağım.

DFA Nedir?

DFA yani Deterministic Finite Automata sonlu sayıda duruma sahip ve her durumdan belirlenen alfabenin tüm harfleri ile bir çıkışa sahip makine türüdür. DFA’lar durum sayıları azaltılarak indirgenebilir ve daha ekonomik ve hızlı çalışan makineler elde edilebilir. Bu açıdan DFA optimizasyonu önemli bir konudur.

DFA Nasıl İndirgenir ?

Aşağıda, resimde yer alan DFA’nın Myphill-Nerode Teoremi ile indirgenmesinin tarifi yer almaktadır.

dfa1

Adım 1: İlk olarak başlangıç durumundan başlayıp erişilemeyen durum varsa o durumu direkt iptal et.

Adım 2: Tüm durum çiftleri için bir tablo oluştur(Qi, Qj)

Adım 3: Çiftleri kontrol et: Eğer durumlardan biri kabul biri red durumuysa o durumu işaretle. (Durum çifti=(Qi,Qj) => Qi ∈ F & Qj ∉ F)

Unutmadan söyleyeyim burada işaretlediğimiz çiftler DFA’da birleşmesi mümkün olmayan durum çiftleridir.

dfa2

Adım 4: Kalan durum çiftlerine sırayla alfabeninin tüm harflerini uygula, eğer aynı harf için gittikleri sonuçlardan biri kabul biri red çıkarsa o çifti de işaretle. 

Adım 5: İşaretlenemez durumlar kalana kadar 4. adımı tekrar et. Eğer işaretlenmemiş çiftler kalırsa, bu DFA minimize edilebilir demektir.

DFA’nın indirgenmiş hali

Umarım bu yazı sizin için yararlı olmuştur. Başka bir yazıda görüşmek dileğiyle, esen kalın.

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Google fotoğrafı

Google hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.