1. DFA: DFA refererer til Deterministic Finite Automaton. En Finite Automata(FA) siges at være deterministisk, hvis der svarer til et inputsymbol, er der en enkelt resulterende tilstand, dvs. der er kun én overgang. En deterministisk endelig automat er et sæt af fem tupler repræsenteret som,
Hvor,
Q: Et ikke-tomt, endeligt sæt af tilstande i den endelige kontrol(qo, q1, q2, …).
Σ: Et ikke-tomt, endeligt sæt af inputsymboler.
δ: Det er en overgangsfunktion, der tager to argumenter, en tilstand og et inputsymbol, den returnerer en enkelt tilstand.
qo: Det er starttilstand, en af tilstandene i Q.
F: Det er et ikke-tomt sæt af sluttilstande/accepterende tilstande fra det sæt, der tilhører Q.
2. ÅRSAGER:
NFA refererer til Nondeterministic Finite Automaton. En Finite Automata(FA) siges at være ikke-deterministisk, hvis der er mere end én mulig overgang fra én tilstand på det samme inputsymbol.
En ikke-deterministisk endelig automat er også et sæt af fem tupler og repræsenteret som,
Hvor,
Q: Et sæt af ikke-tomme endelige tilstande.
Σ: Et sæt ikke-tomme endelige inputsymboler.
δ: Det er en overgangsfunktion, der tager en tilstand fra Q og et inputsymbol fra og returnerer en delmængde af Q.
qo: NFA's oprindelige tilstand og medlem af Q.
F: Et ikke-tomt sæt af endelige stater og medlem af Q.
Forudsætning – Færdig automatisk
Forskellen mellem DFA og NFA:
| DFA | NFA |
|---|---|
| DFA står for Deterministic Finite Automata. | NFA står for Nondeterministic Finite Automata. |
| For hver symbolsk repræsentation af alfabetet er der kun én tilstandsovergang i DFA. | Det er ikke nødvendigt at specificere, hvordan NFA reagerer på et eller andet symbol. |
| DFA kan ikke bruge Empty String-overgang. | NFA kan bruge Empty String transition. |
| DFA kan forstås som én maskine. | NFA kan forstås som flere små maskiner, der regner på samme tid. |
| I DFA er den næste mulige tilstand tydeligt indstillet. | I NFA kan hvert par tilstande og inputsymboler have mange mulige næste tilstande. |
| DFA er sværere at konstruere. | NFA er lettere at konstruere. |
| DFA afviser strengen, hvis den ender i en tilstand, der er forskellig fra den accepterende tilstand. | NFA afviser strengen i tilfælde af, at alle grene dør eller nægter strengen. |
| Den nødvendige tid til at udføre en inputstreng er mindre. | Den nødvendige tid til at udføre en inputstreng er mere. |
| Alle DFA er NFA. | Ikke alle NFA er DFA. |
| DFA kræver mere plads. | NFA kræver mindre plads end DFA. |
| Død konfiguration er ikke tilladt. fx: hvis vi giver input som 0 på q0-tilstand, så skal vi give 1 som input til q0 som selvløkke. | Død konfiguration er tilladt. fx: hvis vi giver input som 0 på q0 tilstand, så vi kan give næste input 1 på q1, som vil gå til næste tilstand. |
| δ: QxΣ -> Q dvs. næste mulige tilstand tilhører Q. | δ: Qx(Σ U ε) -> 2^Q dvs. den næste mulige tilstand tilhører potensmængden af Q. |
| Backtracking er tilladt i DFA. | Backtracking er ikke altid muligt i NFA. |
| Konvertering af regulært udtryk til DFA er vanskelig. | Konvertering af regulært udtryk til NFA er enklere sammenlignet med DFA. |
| Epsilon-flytning er ikke tilladt i DFA | Epsilon-flytning er tilladt i NFA |
| DFA tillader kun ét træk for et enkelt input-alfabet. | Der kan være valg (mere end et træk) for enkelt input alfabet. |