- Finite automater bruges til at genkende mønstre.
- Den tager symbolstrengen som input og ændrer dens tilstand i overensstemmelse hermed. Når det ønskede symbol er fundet, så sker overgangen.
- På overgangstidspunktet kan automaten enten flytte til den næste tilstand eller forblive i den samme tilstand.
- Finite automater har to tilstande, Accepter tilstand eller Afvisningstilstand . Når inputstrengen er behandlet med succes, og automaten nåede sin endelige tilstand, vil den acceptere.
Formel definition af FA
En endelig automat er en samling af 5-tuple (Q, ∑, δ, q0, F), hvor:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Finite Automata Model:
Finite automater kan repræsenteres ved inputtape og finite control.
Inputbånd: Det er et lineært bånd med et vist antal celler. Hvert inputsymbol er placeret i hver celle.
Endelig kontrol: Den endelige kontrol bestemmer den næste tilstand ved modtagelse af bestemt input fra inputbånd. Båndlæseren læser cellerne én efter én fra venstre mod højre, og ad gangen læses kun ét inputsymbol.
Typer af automater:
Der er to typer endelige automater:
- DFA (deterministiske endelige automater)
- NFA (non-deterministic finite automata)
1. DFA
DFA refererer til deterministiske endelige automater. Deterministisk refererer til det unikke ved beregningen. I DFA går maskinen kun til én tilstand for et bestemt inputtegn. DFA accepterer ikke nultrækket.
2. NFA
NFA står for non-deterministic finite automata. Det bruges til at transmittere et vilkårligt antal tilstande for en bestemt input. Den kan acceptere nul-bevægelsen.
Nogle vigtige punkter om DFA og NFA:
- Hver DFA er NFA, men NFA er ikke DFA.
- Der kan være flere sluttilstande i både NFA og DFA.
- DFA bruges i leksikalsk analyse i compiler.
- NFA er mere et teoretisk begreb.