1. DFA: DFA refererer til Deterministic Finite Automaton. En Finite Automata(FA) sies å være deterministisk hvis det tilsvarer et inngangssymbol, det er en enkelt resulterende tilstand, dvs. det er bare en overgang. En deterministisk endelig automat er satt av fem tupler representert som,
Hvor,
Spørsmål: Et ikke-tomt begrenset sett med tilstander i den endelige kontrollen (qo, q1, q2, …).
Σ: Et ikke-tomt begrenset sett med inngangssymboler.
δ: Det er en overgangsfunksjon som tar to argumenter, en tilstand og et inngangssymbol, den returnerer en enkelt tilstand.
qo: Det er starttilstand, en av statene i Q.
F: Det er et ikke-tomt sett med slutttilstander/ aksepterende tilstander fra settet som tilhører Q.
2. ÅRSAKER:
NFA refererer til Nondeterministic Finite Automaton. En Finite Automata(FA) sies å være ikke-deterministisk hvis det er mer enn én mulig overgang fra en tilstand på samme inngangssymbol.
En ikke-deterministisk endelig automat er også et sett med fem tupler og representert som,
Hvor,
Spørsmål: Et sett med ikke-tomme endelige tilstander.
Σ: Et sett med ikke-tomme endelige inngangssymboler.
δ: Det er en overgangsfunksjon som tar en tilstand fra Q og et inngangssymbol fra og returnerer en delmengde av Q.
qo: Opprinnelig tilstand av NFA og medlem av Q.
F: Et ikke-tomt sett med sluttstater og medlem av Q.
Forutsetning – Ferdig med automatisk
Forskjellen mellom DFA og NFA:
| DFA | NFA |
|---|---|
| DFA står for Deterministic Finite Automata. | NFA står for Nondeterministic Finite Automata. |
| For hver symbolsk representasjon av alfabetet er det bare én tilstandsovergang i DFA. | Det er ikke nødvendig å spesifisere hvordan NFA reagerer på et eller annet symbol. |
| DFA kan ikke bruke overgang til tom streng. | NFA kan bruke Empty String-overgang. |
| DFA kan forstås som én maskin. | NFA kan forstås som flere små maskiner som datamaskiner samtidig. |
| I DFA er den neste mulige tilstanden tydelig angitt. | I NFA kan hvert par av tilstand og inngangssymbol ha mange mulige neste tilstander. |
| DFA er vanskeligere å konstruere. | NFA er lettere å konstruere. |
| DFA avviser strengen i tilfelle den avsluttes i en tilstand som er forskjellig fra den aksepterende tilstanden. | NFA avviser strengen i tilfelle alle grener dør eller nekter strengen. |
| Tiden som trengs for å utføre en inndatastreng er mindre. | Tiden som trengs for å utføre en inndatastreng er mer. |
| Alle DFA er NFA. | Ikke alle NFA er DFA. |
| DFA krever mer plass. | NFA krever mindre plass enn DFA. |
| Død konfigurasjon er ikke tillatt. f.eks: hvis vi gir input som 0 på q0-tilstand, så må vi gi 1 som input til q0 som selvsløyfe. | Død konfigurasjon er tillatt. f.eks.: hvis vi gir input som 0 på q0-tilstand, så kan vi gi neste input 1 på q1 som vil gå til neste tilstand. |
| δ: QxΣ -> Q, dvs. neste mulige tilstand tilhører Q. | δ: Qx(Σ U ε) -> 2^Q dvs. neste mulige tilstand tilhører potensmengden til Q. |
| Tilbakesporing er tillatt i DFA. | Tilbakesporing er ikke alltid mulig i NFA. |
| Konvertering av regulære uttrykk til DFA er vanskelig. | Konvertering av regulære uttrykk til NFA er enklere sammenlignet med DFA. |
| Epsilon-flytting er ikke tillatt i DFA | Epsilon-flytting er tillatt i NFA |
| DFA tillater bare ett trekk for alfabet med enkelt inngang. | Det kan være valg (mer enn ett trekk) for alfabet med enkelt input. |