- Äärillisiä automaatteja käytetään kuvioiden tunnistamiseen.
- Se ottaa merkkijonon syötteenä ja muuttaa tilaansa vastaavasti. Kun haluttu symboli löytyy, tapahtuu siirtymä.
- Siirtymähetkellä automaatit voivat joko siirtyä seuraavaan tilaan tai pysyä samassa tilassa.
- Äärillisillä automaateilla on kaksi tilaa, Hyväksy tila tai Hylkää tila . Kun syöttömerkkijono on käsitelty onnistuneesti ja automaatti on saavuttanut lopullisen tilan, se hyväksyy.
FA:n virallinen määritelmä
Äärillinen automaatti on kokoelma 5-monoa (Q, ∑, δ, q0, F), jossa:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Rajallinen automaattimalli:
Äärilliset automaatit voidaan esittää syöttönauhalla ja äärellisellä ohjauksella.
Syötenauha: Se on lineaarinen nauha, jossa on tietty määrä soluja. Jokainen syötesymboli sijoitetaan jokaiseen soluun.
Rajallinen ohjaus: Äärillinen ohjaus päättää seuraavan tilan vastaanottaessaan tietyn tulon syöttönauhalta. Nauhanlukija lukee solut yksitellen vasemmalta oikealle ja kerrallaan luetaan vain yksi syötesymboli.
Automaattityypit:
On olemassa kahdenlaisia äärellisiä automaatteja:
- DFA (deterministinen äärellinen automaatti)
- NFA (ei-deterministinen äärellinen automaatti)
1. DFA
DFA viittaa deterministisiin äärellisiin automaateihin. Deterministisyys viittaa laskennan ainutlaatuisuuteen. DFA:ssa kone siirtyy yhteen tilaan vain tietylle syöttömerkille. DFA ei hyväksy nollasiirtoa.
2. NFA
NFA on lyhenne sanoista ei-deterministinen äärellinen automaatti. Sitä käytetään lähettämään mikä tahansa määrä tiloja tietylle tulolle. Se voi hyväksyä nollasiirron.
Tärkeitä kohtia DFA:sta ja NFA:sta:
- Jokainen DFA on NFA, mutta NFA ei ole DFA.
- Sekä NFA:ssa että DFA:ssa voi olla useita lopullisia tiloja.
- DFA:ta käytetään Compilerin Lexical Analysisissä.
- NFA on enemmänkin teoreettinen käsite.