- Raštams atpažinti naudojami baigtiniai automatai.
- Ji paima simbolio eilutę kaip įvestį ir atitinkamai pakeičia jos būseną. Kai randamas norimas simbolis, įvyksta perėjimas.
- Perėjimo metu automatai gali pereiti į kitą būseną arba likti toje pačioje būsenoje.
- Baigtiniai automatai turi dvi būsenas, Priimti būseną arba Atmesti būseną . Kai įvesties eilutė bus sėkmingai apdorota ir automatas pasieks galutinę būseną, jis priims.
Oficialus FA apibrėžimas
Baigtinis automatas yra 5 kortelių rinkinys (Q, ∑, δ, q0, F), kur:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Baigtinis automato modelis:
Baigtiniai automatai gali būti pavaizduoti įvesties juosta ir baigtiniu valdymu.
Įvesties juosta: Tai linijinė juosta, turinti tam tikrą skaičių langelių. Kiekvienas įvesties simbolis dedamas į kiekvieną langelį.
Baigtas valdymas: Baigtinis valdiklis nusprendžia kitą būseną gavęs tam tikrą įvestį iš įvesties juostos. Juostos skaitytuvas skaito langelius po vieną iš kairės į dešinę ir vienu metu nuskaitomas tik vienas įvesties simbolis.
Automatų tipai:
Yra dviejų tipų baigtiniai automatai:
- DFA (deterministiniai baigtiniai automatai)
- NFA (nedeterministiniai baigtiniai automatai)
1. DFA
DFA reiškia deterministinius baigtinius automatus. Deterministinis reiškia skaičiavimo unikalumą. DFA mašina pereina į vieną būseną tik tam tikram įvesties simboliui. DFA nepriima nulinio judėjimo.
2. NFA
NFA reiškia nedeterministinius baigtinius automatus. Jis naudojamas perduoti bet kokį tam tikros įvesties būsenų skaičių. Jis gali priimti nulinį žingsnį.
Keletas svarbių dalykų apie DFA ir NFA:
- Kiekvienas DFA yra NFA, bet NFA nėra DFA.
- Tiek NFA, tiek DFA gali būti kelios galutinės būsenos.
- DFA naudojama kompiliatoriaus leksinėje analizėje.
- NFA yra daugiau teorinė sąvoka.