Forskjell mellom NFA og DFA Forskjellen mellom

NFA vs DFA

Teorien om beregning er en gren av datavitenskap som omhandler hvordan problemer løses ved hjelp av algoritmer. Den har tre grener, nemlig; den beregningsmessige kompleksitetsteorien, beregningsteorien og automatteori.

Automaten eller automatteori er studiet av abstrakte matematiske maskiner eller systemer som kan brukes til å løse beregningsproblemer. En automat består av stater og overganger, og som det ser et symbol eller et brev av inngang, gjør det en overgang til en annen stat som tar gjeldende tilstand og symbol som input.

Automaten eller automatteori har flere klasser som inkluderer Deterministic Finite Automata (DFA) og Nondeterministic Finite Automata (NFA). Disse to klassene er overgangsfunksjoner av automat eller automat.

I overgang kan DFA ikke bruke n tom streng, og det kan forstås som en maskin. Hvis strengen slutter i en tilstand som ikke er en akseptabel tilstand, vil DFA avvise det. En DFA-maskin kan bygges med hver inngang og utgang.

DFA har bare en tilstandsovergang for hvert symbol på alfabetet, og det er bare en sluttstat for overgangen, noe som betyr at for hver karakter som er lest, er det en tilsvarende stat i DFA. Det er enklere å sjekke medlemskap i DFA, men det er vanskeligere å konstruere. Backtracking er tillatt i DFA, og det krever mer plass enn NFA.

Backtracking er ikke alltid tillatt i NFA. Mens det er mulig i noen tilfeller, er det ikke i andre. Det er lettere å konstruere NFA, og det krever også mindre plass, men det er ikke mulig å konstruere en NFA-maskin for hver inngang og utgang.

Det forstås som flere små maskiner som beregner samtidig, og medlemskapet kan være vanskeligere å sjekke. Det bruker Empty String Transition, og det er mange mulige neste stater for hvert par av stat og inngangssymbol. Den starter i en bestemt tilstand og leser symbolene, og automaten bestemmer deretter neste tilstand som avhenger av gjeldende inngang og andre tilhørende hendelser. Ved aksepttilstand aksepterer NFA strengen og avviser det ellers.

Sammendrag:

1. "DFA" står for "Deterministic Finite Automata" mens "NFA" står for "Nondeterministic Finite Automata. “

2. Begge er overgangsfunksjoner av automata. I DFA er neste mulige tilstand tydelig innstilt mens i NFA hvert par stat og inngangssymbol kan ha mange mulige neste stater.

3. NFA kan bruke tom strengovergang, mens DFA ikke kan bruke tom strengovergang.

4. NFA er lettere å konstruere, mens det er vanskeligere å konstruere DFA.

5. Backtracking er tillatt i DFA mens i NFA det kan eller ikke er tillatt.

6. DFA krever mer plass mens NFA krever mindre plass.

7. Mens DFA kan forstås som en maskin og en DFA-maskin kan bygges for hver inngang og utgang, kan 8. NFA forstås som flere små maskiner som beregner sammen, og det er ingen mulighet for å konstruere en NFA-maskin for hver inngang og utgang.