NFA ve DFA Arasındaki Fark

NFA ve DFA

Hesaplama teorisi, bilgisayar biliminin, algoritmaları kullanarak problemlerin nasıl çözüldüğünü anlatan bir dalıdır. Üç şubesi vardır; hesaplama karmaşıklığı teorisi, hesaplanabilirlik teorisi ve otomat teorisi.

Otomasyon veya otomata teorisi, hesaplama problemlerini çözmek için kullanılabilen soyut matematiksel makinelerin veya sistemlerin çalışmasıdır. Bir otomat devletlerden ve geçişlerden oluşur ve bir sembol veya harf harfi gördüğünden, mevcut durumu ve sembolü girdi olarak başka bir devlete geçiş yapar.

Otomat veya otomata teorisi, Deterministik Sonlu Otomasyon (DFA) ve Netermetermistic Sonlu Otomasyon (NFA) gibi çeşitli sınıflara sahiptir. Bu iki sınıf, otomata veya otomatın geçiş işlevidir.

Geçişte, DFA n boş dize kullanamaz ve bir makine olarak anlaşılabilir. Dize kabul edilebilir bir durum olmayan bir durumda biterse, DFA onu reddeder. Her giriş ve çıkış ile bir DFA makinesi oluşturulabilir.

DFA yalnızca alfabenin her sembolü için bir durum geçişi içerir ve geçiş için yalnızca bir son durum vardır; bu, okunan her karakter için DFA'da bir karşılık gelen durum anlamına gelir. DFA üyeliğini kontrol etmek daha kolalı, ancak kurulması daha zor. DFA'da geri izlemeye izin verilir ve NFA'dan daha fazla alan gerektirir.

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

Eşzamanlı olarak hesaplanan birkaç küçük makine olarak anlaşılıyor ve üyelik denetimi zorlaşıyor. Boş Dize Geçişini kullanır ve her bir durum çifti ve giriş simgesi için çok sayıda olası sonraki durum vardır. Belli bir durumda başlar ve sembolleri okur ve otomat sonra mevcut girdiye ve diğer olaylara bağlı olan bir sonraki durumu belirler. Kabul edici durumunda NFA dizeyi kabul eder ve aksini reddeder.

Özet:

1. "DFA", "Deterministic Finite Automata" yı, "NFA" ise "Nondeterministic Finite Automata" yı temsil ediyor. “2

. Her ikisi de otomata geçiş işlevidir. DFA'da bir sonraki muhtemel durum belirgin şekilde ayarlanırken, NFA'da her bir durum çifti ve girdi sembolü birçok muhtemel sonraki duruma sahip olabilir.

3. DFA boş dize geçişini kullanamazken NFA boş dize geçişini kullanabilir.

4. NFA, DFA oluşturmak daha zor olsa da inşa etmek daha kolaydır.

5. DFA'da geri izlemeye izin verilirken, NFA'da izin verilebilir veya izin verilmeyebilir.

6. NFA daha az alan gerektirirken, DFA daha fazla alan gerektirir.

7. DFA bir makine, bir DFA makinesi her girdi ve çıktı için oluşturulabilirken, 8. NFA birlikte hesaplanan birkaç küçük makine olarak anlaşılabilir ve her giriş ve çıkış için bir NFA makinesi inşa etme olasılığı yoktur.