Разлика между NFA и DFA

NFA срещу DFA

Теорията на изчисленията е клон на компютърните науки, който се занимава с това как проблемите се решават с помощта на алгоритми. Той има три клона, а именно; теорията за сложността на изчисленията, теорията за изчислимостта и теорията на автоматите.

Теорията за автоматика или автоматите е изучаването на абстрактни математически машини или системи, които могат да бъдат използвани за решаване на изчислителни задачи. Автоматът е съставен от състояния и преходи и тъй като вижда символ или буква на въвеждане, той прави преход към друго състояние, като приема текущото състояние и символ като вход.

Теорията на автоматика или автоматите има няколко класа, които включват Детерминирани Крайни Автомати (DFA) и Недетерминирани Крайни Автомати (NFA). Тези два класа са преходни функции на автомати или автомати.

В преход DFA не може да използва n празен низ и може да бъде разбран като една машина. Ако низът завърши в състояние, което не е приемливо състояние, DFA ще го отхвърли. DFA машина може да бъде конструирана с всеки вход и изход.

DFA има само един преход на състоянието за всеки символ от азбуката и има само едно крайно състояние за неговия преход, което означава, че за всеки символ, който се чете, има едно съответно състояние в DFA. По-лесно е да се провери членството в DFA, но е по-трудно да се изгради. Обратното проследяване е позволено в DFA и изисква повече пространство от NFA.

Обратното проследяване не винаги е позволено в NFA. Докато в някои случаи е възможно, в други не е така. По-лесно е да се конструира NFA и това също изисква по-малко пространство, но не е възможно да се конструира NFA машина за всеки вход и изход.

Той се разбира като няколко малки машини, които се изчисляват едновременно и членството може да бъде по-трудно да се провери. Той използва празен стринг преход и има множество възможни следващи състояния за всяка двойка състояние и входен символ. Той започва в определено състояние и чете символите, а след това автоматът определя следващото състояние, което зависи от текущия вход и други последващи събития. В своето състояние на приемане, NFA приема низ и го отхвърля по друг начин.

Резюме:

1. „DFA“ означава „Детерминирани крайни автомати“, докато „NFA“ означава „Недетерминирани крайни автомати“.
2.Both са функции за преход на автомати. В DFA следващото възможно състояние е ясно зададено, докато в NFA всяка двойка състояние и входен символ може да има много възможни следващи състояния.
3.NFA може да използва преход на празен низ, докато DFA не може да използва преход на празен низ.
4.NFA е по-лесно да се конструира, докато е по-трудно да се конструира DFA.
5.Backtracking е позволено в DFA, докато в NFA може или не може да бъде позволено.
6.DFA изисква повече пространство, докато NFA изисква по-малко пространство.
7.Докато DFA може да се разбира като една машина и DFA машина може да бъде конструирана за всеки вход и изход, 8.NFA може да се разбира като няколко малки машини, които изчисляват заедно, и няма възможност за конструиране на NFA машина за всеки вход и изход.