DFA Minimization
Aynı düzenli dili kabul eden DFA'yı davranışça eşdeğer durumları birleştirerek en az durumlu eşdeğer otomata dönüştürme işlemi.
DFA minimizasyonunda amaç yalnız ulaşılamayan state'leri silmek değildir. Asıl işlem, gelecekteki bütün input dizileri için ayırt edilemeyen state'leri aynı eşdeğerlik sınıfında toplamaktır.
Partition Refinement
Hopcroft yaklaşımı accepting ve non-accepting state'lerle başlayan bir partition'ı, transition davranışı ayrım gerektirdikçe böler. Uygun veri yapısıyla klasik karmaşıklık O(|Sigma| * n log n) düzeyindedir.
Regex/lexer üretimi, protocol parser ve model tabanlı test araçlarında minimal state sayısı yalnız bellek kazancı sağlamaz; generated table ve geçiş davranışını da sadeleştirir.
Sınır
NFA minimizasyonu aynı problem değildir. Önce determinization yapılması state explosion üretebilir ve minimal DFA'nın küçük olması ara determinization maliyetinin küçük olacağını garanti etmez.
Kaynak
- https://arxiv.org/abs/1010.5318