1. DFA: DFA hänvisar till Deterministic Finite Automaton. En Finite Automata(FA) sägs vara deterministisk om det motsvarar en ingångssymbol, det finns ett enda resulterande tillstånd, dvs det finns bara en övergång. En deterministisk finit automat är en uppsättning av fem tupler representerade som,
Var,
F: En icke-tom finit uppsättning tillstånd i den finita kontrollen (qo, q1, q2, …).
Σ: En icke-tom ändlig uppsättning ingångssymboler.
δ: Det är en övergångsfunktion som tar två argument, ett tillstånd och en ingångssymbol, den returnerar ett enda tillstånd.
qo: Det är starttillstånd, en av tillstånden i Q.
F: Det är en icke-tom uppsättning sluttillstånd/accepterande tillstånd från uppsättningen som tillhör Q.
2. ORSAKER:
NFA hänvisar till Nondeterministic Finite Automaton. En Finite Automata(FA) sägs vara icke-deterministisk om det finns mer än en möjlig övergång från ett tillstånd på samma ingångssymbol.
En icke-deterministisk finit automat är också en uppsättning av fem tupler och representeras som,
Var,
F: En uppsättning icke-tomma ändliga tillstånd.
Σ: En uppsättning icke tomma finita ingångssymboler.
δ: Det är en övergångsfunktion som tar ett tillstånd från Q och en ingångssymbol från och returnerar en delmängd av Q.
qo: Initialt tillstånd för NFA och medlem av Q.
F: En icke-tom uppsättning slutstater och medlem av Q.
Förutsättning – Färdig automatisk
Skillnaden mellan DFA och NFA:
| DFA | NFA |
|---|---|
| DFA står för Deterministic Finite Automata. | NFA står för Nondeterministic Finite Automata. |
| För varje symbolisk representation av alfabetet finns det bara en tillståndsövergång i DFA. | Du behöver inte specificera hur NFA reagerar enligt någon symbol. |
| DFA kan inte använda Empty String-övergång. | NFA kan använda Empty String-övergång. |
| DFA kan förstås som en maskin. | NFA kan förstås som flera små maskiner som datorer samtidigt. |
| I DFA är nästa möjliga tillstånd distinkt inställt. | I NFA kan varje par av tillstånd och ingångssymboler ha många möjliga nästa tillstånd. |
| DFA är svårare att konstruera. | NFA är lättare att konstruera. |
| DFA avvisar strängen om den avslutas i ett tillstånd som skiljer sig från det accepterande tillståndet. | NFA avvisar strängen i händelse av att alla grenar dör eller vägrar strängen. |
| Tiden som behövs för att exekvera en inmatningssträng är mindre. | Tiden som krävs för att exekvera en inmatningssträng är längre. |
| Alla DFA är NFA. | Alla NFA är inte DFA. |
| DFA kräver mer utrymme. | NFA kräver mindre utrymme än DFA. |
| Död konfiguration är inte tillåten. t.ex.: om vi ger indata som 0 på q0-tillstånd så måste vi ge 1 som ingång till q0 som självslinga. | Död konfiguration är tillåten. t.ex.: om vi ger ingången som 0 på q0-tillståndet så kan vi ge nästa ingång 1 på q1 som kommer att gå till nästa tillstånd. |
| δ: QxΣ -> Q, dvs nästa möjliga tillstånd tillhör Q. | δ: Qx(Σ U ε) -> 2^Q, dvs nästa möjliga tillstånd tillhör maktmängden Q. |
| Backtracking är tillåtet i DFA. | Backtracking är inte alltid möjligt i NFA. |
| Konvertering av reguljära uttryck till DFA är svårt. | Konvertering av reguljära uttryck till NFA är enklare jämfört med DFA. |
| Epsilon-flytt är inte tillåtet i DFA | Epsilon-flytt är tillåtet i NFA |
| DFA tillåter endast ett drag för enstaka inmatningsalfabet. | Det kan finnas val (mer än ett drag) för enstaka inmatningsalfabet. |