TechCodeview

• Finite state-maskin brukes til å gjenkjenne mønstre.
• Finite automata-maskin tar symbolstrengen som input og endrer tilstanden tilsvarende. I inngangen, når et ønsket symbol er funnet, skjer overgangen.
• Under overgangen kan automaten enten flytte til neste tilstand eller forbli i samme tilstand.
• FA har to stater: akseptere stat eller avvise stat. Når inndatastrengen er vellykket behandlet og automaten nådde sin endelige tilstand, vil den godta.

En endelig automat består av følgende:

Spørsmål: begrenset sett med tilstander
∑: begrenset sett med inngangssymbol
q0: utgangstilstand
F: slutttilstand
d: Overgangsfunksjon

Overgangsfunksjon kan defineres som

 δ: Q x ∑ →Q 

FA karakteriseres på to måter:

1. DFA (endelig automat)
2. NDFA (ikke-deterministiske endelige automater)

DFA

DFA står for Deterministic Finite Automata. Deterministisk refererer til det unike ved beregningen. I DFA går inndatategnet kun til én tilstand. DFA godtar ikke nulltrekket som betyr at DFA ikke kan endre tilstand uten noe inndatategn.

DFA har fem tupler {Q, ∑, q0, F, δ}

Eksempel

Se et eksempel på deterministiske endelige automater:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 

NDFA

NDFA refererer til Non Deterministic Finite Automata. Den brukes til å overføre et hvilket som helst antall stater for en bestemt inngang. NDFA aksepterer NULL-trekket som betyr at det kan endre tilstand uten å lese symbolene.

NDFA har også fem stater samme som DFA. Men NDFA har en annen overgangsfunksjon.

Overgangsfunksjonen til NDFA kan defineres som:

Eksempel

Se et eksempel på ikke-deterministiske endelige automater:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3}