Finite Automata(FA) on yksinkertaisin kone kuvioiden tunnistamiseen. Sitä käytetään säännöllisen kielen karakterisoimiseen, esimerkiksi: /baa+!/.
Sitä käytetään myös luonnollisen kielen ilmaisujen analysointiin ja tunnistamiseen. Äärillinen automaatti tai äärellinen kone on abstrakti kone, jossa on viisi elementtiä tai monikkoa. Siinä on joukko tiloja ja sääntöjä tilasta toiseen siirtymiseen, mutta se riippuu käytetystä syöttösymbolista. Tilan ja sääntöjoukon perusteella syötemerkkijono voidaan joko hyväksyä tai hylätä. Pohjimmiltaan se on abstrakti malli digitaalisesta tietokoneesta, joka lukee syötemerkkijonon ja muuttaa sen sisäistä tilaa riippuen nykyisestä syöttösymbolista. Jokainen automaatti määrittelee kielen eli joukon merkkijonoja, jotka se hyväksyy. Seuraava kuva esittää joitakin yleisen automaation olennaisia piirteitä.
Kuva: Finite Automatan ominaisuudet
Yllä oleva kuva näyttää seuraavat automaatin ominaisuudet:
java esimerkki
- Syöte
- Lähtö
- Automaattien tilat
- Valtion suhde
- Tuotossuhde
Finite Automata koostuu seuraavista:
Q : Finite set of states. ? : set of Input Symbols. q : Initial state. F : set of Final States. ? : Transition Function.>
Koneen muodollinen määritys on
{ Q, ?, q, F, ? }> FA luokitellaan kahteen tyyppiin:
1) Deterministinen äärellinen automaatti (DFA):
DFA consists of 5 tuples {Q, ?, q, F, ?}. Q : set of all states. ? : set of input symbols. ( Symbols which machine takes as input ) q : Initial state. ( Starting state of a machine ) F : set of final state. ? : Transition Function, defined as ? : Q X ? -->Q.> DFA:ssa kone siirtyy tietylle syöttömerkille vain yhteen tilaan. Siirtymäfunktio määritellään jokaisessa tilassa jokaiselle tulosymbolille. Myöskään DFA:ssa nolla (tai ?) siirto ei ole sallittu, eli DFA ei voi muuttaa tilaa ilman syötettä.
Luo esimerkiksi DFA, joka hyväksyy kielen, jossa on kaikki merkkijonot, jotka päättyvät 'a'.
Annettu: ? = {a,b}, q = {q0}, F={q1}, Q = {q0, q1}
Harkitse ensin kielijoukkoa kaikista mahdollisista hyväksyttävistä merkkijonoista, jotta voit muodostaa tarkan tilasiirtymäkaavion.
L = {a, aa, aaa, aaaa, aaaaa, ba, bba, bbba, isä, isä, isä, isä}
Yllä on yksinkertainen osajoukko mahdollisista hyväksyttävistä merkkijonoista, ja siellä voi olla monia muita merkkijonoja, jotka päättyvät 'a' ja sisältävät symboleja {a,b}.
Kuva 1. Tilasiirtymäkaavio DFA:lle, jossa on ? = {a, b}
Merkkijonoja ei hyväksytä ovat,
ab, bb, aab, abbb jne.
Tilasiirtymätaulukko yllä olevalle automaatille,
| ?OsavaltioSymboli? | a | b |
|---|---|---|
| q0 | q1 | q0 |
| q1 | q1 | q0 |
Yksi tärkeä huomioitava asia on, kuviolle voi olla monia mahdollisia DFA:ita . DFA, jossa on vähimmäismäärä tiloja, on yleensä edullinen.
2) Epädeterministinen äärellinen automaatti (NFA): NFA on samanlainen kuin DFA, lukuun ottamatta seuraavia lisäominaisuuksia:
- Nolla (tai ?) liike on sallittu, eli se voi siirtyä eteenpäin lukematta symboleja.
- Mahdollisuus lähettää mihin tahansa määrään tiloja tietylle tulolle.
Nämä yllä olevat ominaisuudet eivät kuitenkaan lisää NFA:ta tehoa. Jos vertaamme molempia tehon suhteen, molemmat ovat samanarvoisia.
Yllä olevien lisäominaisuuksien vuoksi NFA:lla on erilainen siirtymätoiminto, loput ovat samat kuin DFA.
?: Transition Function ?: Q X (? U ? ) -->2 ^ Q.>>Kuten näet siirtymäfunktiosta, joka on tarkoitettu mille tahansa syötteelle, mukaan lukien nolla (tai ?), NFA voi mennä mihin tahansa tilojen määrään. Esimerkiksi alla on NFA yllä olevalle ongelmalle.
Kuva 2. Tilasiirtymäkaavio NFA:lle, jossa on ? = {a, b}
Tilasiirtymätaulukko yllä olevalle automaatille,
| ?OsavaltioSymboli? | a | b |
|---|---|---|
| q0 | {q0,q1} | q0 |
| q1 | ? | ? |
Yksi tärkeä huomioitava asia on, NFA:ssa, jos jokin syöttömerkkijonon polku johtaa lopulliseen tilaan, syötemerkkijono On hyväksytty . Esimerkiksi yllä olevassa NFA:ssa syötemerkkijonolle 00 on useita polkuja. Koska yksi poluista johtaa lopulliseen tilaan, yllä oleva NFA hyväksyy arvon 00.
Joitakin tärkeitä kohtia:
hakkeroinnin käsittely
- Perustelut: