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.
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.
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.
Umarım bu yazı sizin için yararlı olmuştur. Başka bir yazıda görüşmek dileğiyle, esen kalın.
Erkan Ceylan 