NFA ve DFA Arasındaki Fark

NFA ve DFA

Hesaplama teorisi, problemlerin algoritmalar kullanılarak nasıl çözüldüğünü ele alan bilgisayar biliminin bir dalıdır. Üç şubesi vardır; hesaplamalı karmaşıklık teorisi, hesaplanabilirlik teorisi ve otomat teorisi.

Otomat veya otomat teorisi, hesaplama problemlerini çözmek için kullanılabilecek soyut matematiksel makineler veya sistemlerin incelenmesidir. Bir otomasyon durumlardan ve geçişlerden oluşur ve bir sembol veya girdi mektubu gördüğü için, mevcut durumu ve sembolü giriş olarak alan başka bir duruma geçiş yapar.

Otomat veya otomat teorisinin Deterministik Sonlu Otomata (DFA) ve Belirsiz Sonlu Otomata (NFA) içeren birkaç sınıfı vardır. Bu iki sınıf, otomatların veya otomatların geçiş fonksiyonlarıdır.

Geçişte, DFA n boş dize kullanamaz ve tek bir makine olarak anlaşılabilir. Dize kabul edilebilir bir durumla bitmezse, DFA dizeyi reddeder. Her giriş ve çıkışla bir DFA makinesi yapılabilir.

DFA, alfabenin her sembolü için yalnızca bir durum geçişine sahiptir ve geçişi için yalnızca bir son durum vardır, bu da okunan her karakter için DFA'da karşılık gelen bir durum olduğu anlamına gelir. DFA üyeliğini kontrol etmek daha kolaydır, ancak yapılandırılması daha zordur. DFA'da geri izlemeye izin verilir ve NFA'dan daha fazla alan gerektirir.

NFA'da geri izlemeye her zaman izin verilmez. Bazı durumlarda mümkün olsa da, bazılarında mümkün değildir. NFA oluşturmak daha kolaydır ve daha az yer gerektirir, ancak her giriş ve çıkış için bir NFA makinesi oluşturmak mümkün değildir.

Aynı anda hesaplayan birkaç küçük makine olarak anlaşılır ve üyeliği kontrol etmek daha zor olabilir. Boş String Geçişini kullanır ve her bir durum çifti ve giriş sembolü için birçok olası sonraki durum vardır. Belirli bir durumda başlar ve sembolleri okur ve otomat daha sonra geçerli girdiye ve diğer olaylara bağlı olan bir sonraki durumu belirler. Kabul etme durumunda, NFA dizeyi kabul eder ve aksini reddeder.

Özet:

1. “DFA” “Deterministik Sonlu Otomata”, “NFA” ise “Belirsiz Sonlu Otomata” anlamına gelir.
2.Her iki otomatanın geçiş fonksiyonlarıdır. DFA'da bir sonraki olası durum belirgin bir şekilde ayarlanırken, NFA'da her bir durum çifti ve giriş sembolü birçok olası sonraki duruma sahip olabilir.
3. DFA boş dize geçişini kullanırken boş dize geçişini kullanabilir.
4. DFA inşa etmek daha kolayken DFA inşa etmek daha zordur.
5. DFA'da geri izlemeye izin verilirken, NFA'da izin verilebilir veya verilmeyebilir.
6. DFA daha fazla alan gerektirirken, NFA daha az alan gerektirir.
7. DFA bir makine olarak anlaşılabilirken ve her giriş ve çıkış için bir DFA makinesi oluşturulabilirken, 8.NFA birlikte hesaplayan birkaç küçük makine olarak anlaşılabilir ve her giriş için bir NFA makinesi oluşturma imkanı yoktur. ve çıktı.