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

NFA срещу DFA

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

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

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

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

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

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

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

Резюме:

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

28 коментара

  1. NFA ПОТРЕБЯВА ПОВЕЧЕ ПРОСТРАНСТВО И DFA ИЗИСКВА ПО -МЯСТО ПРОСТРАНСТВО ... ...

  2. Докато DFA може да се разбира като една машина и DFA машина може да бъде конструирана за всеки вход и изход, NFA може да се разбира като няколко малки машини, които изчисляват заедно, и няма възможност за конструиране на NFA машина за всеки вход и изход. защо?

  3. благодаря на priyanka за въпроса ... благодаря на neha за отговора на правилен отговор ... по -сгрешил си, грешиш ...

    • Уважаеми Саалия Муртаза Халид: Най фасни джавана, тере коло най фари джани.

      • и двамата грешите, няма nfa и dfa в процеса на автоматизация има нов процес, който се добавя към списъка, известен като FSA, който е ултиматум на всички други процеси, които са необходими за доказване на теоремите на изчислението процес.

  4. Анджу, може да бъде. Но тогава това би било само DFA. Можете да мислите, че Dfa е подмножество на nfa

  5. да точно неха

  6. Не е задължително nfa да се конструира лесно от dfa.

  7. Аз съм студент .... Посочените по -горе твърдения са момчета от r8, не се обърквайте, като слушате всички tge над глупавите коментари ...

  8. Dfa изисква повече място, защото има само едно крайно състояние и трябва да направим само едно състояние от друго, където както в nfa можем да направим множество и можем да имаме повече от едно крайно състояние

  9. plz обясняват състоянието на FA и NFA

  10. може ли да се представи краен автомат?

  11. в номер 7 защо и двамата са DFA. кой е за DFA.

  12. съжалявам, че разбрах сега ...

  13. DFA има повече място, а NFA има по -малко място

  14. DFA изисква повече място от NFA

Вижте повече за: