NFA-DFA Çevirici
Geçiş tablosu ve kabul durumları verilen bir NFA'nın ulaşılabilir durum kümelerini çıkararak eşdeğer DFA gösterimine dönüştürülmesini ele alan proje.
Bu proje, geçiş tablosu ve kabul durumları verilen bir deterministik olmayan sonlu otomatı (NFA), aynı dili kabul eden deterministik sonlu otomata (DFA) dönüştürme problemini ele alıyordu.
Durum Kümesi Yaklaşımı
DFA'daki tek bir durum, NFA'da aynı girdi ön eki sonrasında bulunulabilecek birden fazla durumun kümesini temsil edebilir. Dönüşüm bu nedenle NFA durumlarını tek tek kopyalamak yerine ulaşılabilir durum kümelerini üretir.
Başlangıç kümesinden itibaren her giriş sembolü için erişilebilen NFA durumları hesaplanır. Daha önce görülmemiş bir küme ortaya çıktığında bu küme yeni bir DFA durumu olarak işleme alınır. Ulaşılabilir yeni küme kalmayıncaya kadar süreç devam eder.
Bir DFA durumu olarak temsil edilen küme, NFA'nın kabul durumlarından en az birini içeriyorsa kabul durumu olarak işaretlenir.
Determinizmin Sağlanması
NFA aynı durum ve sembol için birden fazla olası geçişe izin verebilir. DFA'da ise her durum-sembol çifti için tek hedef gerekir. Durum kümeleri bu çoklu olasılığı tek deterministik geçiş tablosuna dönüştürür.
Epsilon geçişleri kullanılan bir NFA varyantında ayrıca epsilon-closure hesabı gerekir; bu eski proje sayfasındaki kayıt, uygulamanın bütün giriş biçimlerini belgelemediği için burada desteklenmeyen bir özelliği varmış gibi sunmuyorum.
Teorik Bağlam
Dönüşümün daha geniş teorik çerçevesi Otomatlar Kuramı ve Biçimsel Diller notlarımda yer alıyor. Projenin değeri, biçimsel bir eşdeğerlik sonucunu doğrudan çalıştırılabilir durum-tablosu algoritmasına dönüştürmesidir.
