- Äärillisen tilan konetta käytetään kuvioiden tunnistamiseen.
- Äärillinen automaatio ottaa syötteeksi merkkijonon ja muuttaa sen tilaa vastaavasti. Syöttössä, kun haluttu symboli löytyy, tapahtuu siirtymä.
- Siirtymisen aikana automaatit voivat joko siirtyä seuraavaan tilaan tai pysyä samassa tilassa.
- FA:lla on kaksi tilaa: hyväksyntätila tai hylkäystila. Kun syötemerkkijono on käsitelty onnistuneesti ja automaatti on saavuttanut lopullisen tilan, se hyväksyy sen.
Äärillinen automaatti koostuu seuraavista:
K: äärellinen joukko tiloja
∑: rajallinen joukko syöttösymboleja
q0: alkutila
F: lopullinen tila
d: Siirtymätoiminto
Siirtymäfunktio voidaan määritellä seuraavasti
δ: Q x ∑ →Q
FA luonnehditaan kahdella tavalla:
- DFA (finite automata)
- NDFA (ei-deterministiset äärelliset automaatit)
DFA
DFA on lyhenne sanoista Deterministic Finite Automata. Deterministisyys viittaa laskennan ainutlaatuisuuteen. DFA:ssa syöttömerkki siirtyy vain yhteen tilaan. DFA ei hyväksy nollasiirtoa, mikä tarkoittaa, että DFA ei voi muuttaa tilaa ilman syöttömerkkiä.
DFA:ssa on viisi monikkoa {Q, ∑, q0, F, δ}
K: kaikkien tilojen joukko∑: tulosymbolien äärellinen joukko, jossa δ: Q x ∑ →Q
q0: alkutila
F: lopullinen tila
d: Siirtymätoiminto
Esimerkki
Katso esimerkki deterministisista äärellisistä automaateista:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 
NDFA
NDFA viittaa epädeterministisiin äärellisiin automaateihin. Sitä käytetään siirtämään minkä tahansa määrän tiloja tietylle syötteelle. NDFA hyväksyy NULL-siirron, mikä tarkoittaa, että se voi muuttaa tilaa lukematta symboleja.
NDFA:lla on myös viisi tilaa, jotka ovat samat kuin DFA:lla. Mutta NDFA:lla on erilainen siirtymätoiminto.
NDFA:n siirtymäfunktio voidaan määritellä seuraavasti:
d: Q x ∑ →2KEsimerkki
Katso esimerkki ei-deterministisistä äärellisistä automaateista:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 