- Finite automater brukes til å gjenkjenne mønstre.
- Den tar symbolstrengen som input og endrer tilstanden tilsvarende. Når ønsket symbol er funnet, skjer overgangen.
- På overgangstidspunktet kan automaten enten flytte til neste tilstand eller forbli i samme tilstand.
- Finite automater har to tilstander, Godta staten eller Avvise tilstand . Når inndatastrengen er behandlet vellykket, og automaten nådde sin endelige tilstand, vil den godta.
Formell definisjon av FA
En endelig automat er en samling av 5-tuppel (Q, ∑, δ, q0, F), der:
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 representeres ved inngangstape og endelig kontroll.
Inndatabånd: Det er et lineært bånd med et visst antall celler. Hvert inngangssymbol er plassert i hver celle.
Endelig kontroll: Den endelige kontrollen bestemmer neste tilstand ved mottak av spesielle input fra inndatabånd. Båndleseren leser cellene én etter én fra venstre mot høyre, og av gangen leses kun ett inngangssymbol.
Typer automater:
Det finnes to typer endelige automater:
- DFA (deterministiske endelige automater)
- NFA (ikke-deterministiske endelige automater)
1. DFA
DFA refererer til deterministiske endelige automater. Deterministisk refererer til det unike ved beregningen. I DFA går maskinen kun til én tilstand for et bestemt inndatategn. DFA godtar ikke nulltrekket.
2. NFA
NFA står for ikke-deterministiske endelige automater. Den brukes til å overføre et hvilket som helst antall tilstander for en bestemt inngang. Den kan godta nulltrekket.
Noen viktige punkter om DFA og NFA:
- Hver DFA er NFA, men NFA er ikke DFA.
- Det kan være flere slutttilstander i både NFA og DFA.
- DFA brukes i leksikalsk analyse i kompilator.
- NFA er mer et teoretisk konsept.