Forskel mellem NFA og DFA Forskel mellem

NFA vs DFA

Teorien om beregning er en gren af ​​datalogi, der beskæftiger sig med, hvordan problemer løses ved hjælp af algoritmer. Det har tre grene, nemlig; den beregningsmæssige kompleksitetsteori, beregnelighedsteorien og automatteorien.

Automaten eller automattheoretikken er undersøgelsen af ​​abstrakte matematiske maskiner eller systemer, som kan bruges til at løse computervanskeligheder. En automat består af stater og overgange, og som det ser et symbol eller et brev af input, overgår det til en anden tilstand, der tager den nuværende tilstand og symbolet som input.

Automaten eller automattheoretikken har flere klasser, der omfatter Deterministic Finite Automata (DFA) og Nondeterministic Finite Automata (NFA). Disse to klasser er overgangsfunktioner af automat eller automat.

I overgang kan DFA ikke bruge n tom streng, og det kan forstås som en maskine. Hvis strengen slutter i en tilstand, der ikke er en acceptabel tilstand, vil DFA afvise det. En DFA-maskine kan konstrueres med hver indgang og udgang.

DFA har kun en tilstandsovergang for hvert symbol på alfabetet, og der er kun en endelige tilstand for overgangen, hvilket betyder at for hver tegn, der læses, er der en tilsvarende tilstand i DFA. Det er nemmere at kontrollere medlemskab i DFA, men det er sværere at konstruere. Backtracking er tilladt i DFA, og det kræver mere plads end NFA.

Backtracking er ikke altid tilladt i NFA. Mens det er muligt i nogle tilfælde, er det ikke i andre. Det er lettere at konstruere NFA, og det kræver også mindre plads, men det er ikke muligt at konstruere en NFA-maskine for hver indgang og udgang.

Det forstås som flere små maskiner, der beregner samtidigt, og medlemskab kan være sværere at kontrollere. Det bruger Empty String Transition, og der er mange mulige næste stater for hvert par af stat og indgangssymbol. Den starter i en bestemt tilstand og læser symbolerne, og automaten bestemmer derefter den næste tilstand, der afhænger af den aktuelle indgang og andre hermed forbundne hændelser. I sin accepterende tilstand accepterer NFA strengen og afviser det ellers.

Sammendrag:

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

2. Begge er overgangsfunktioner af automata. I DFA er den næste mulige tilstand tydeligt indstillet, mens i NFA hvert par stat og indgangssymbol kan have mange mulige næste tilstande.

3. NFA kan bruge tom streng overgang, mens DFA ikke kan bruge tom snor overgang.

4. NFA er lettere at konstruere, mens det er sværere at konstruere DFA.

5. Backtracking er tilladt i DFA, mens det i NFA er tilladt eller ej.

6. DFA kræver mere plads, mens NFA kræver mindre plads.

7. Mens DFA kan forstås som en maskine, og en DFA-maskine kan konstrueres for hver indgang og udgang, kan 8. NFA forstås som flere små maskiner, der beregner sammen, og der er ingen mulighed for at konstruere en NFA-maskine til hver indgang og udgang.