Finite Automata (FA) yra paprasčiausias aparatas, atpažįstantis šablonus. Jis naudojamas apibūdinti įprastą kalbą, pavyzdžiui: /baa+!/.
Taip pat jis naudojamas natūralios kalbos išraiškoms analizuoti ir atpažinti. Baigtiniai automatai arba baigtinių būsenų mašina yra abstrakti mašina, turinti penkis elementus arba eilutes. Jis turi būsenų ir taisyklių rinkinį, skirtą pereiti iš vienos būsenos į kitą, tačiau tai priklauso nuo taikomo įvesties simbolio. Atsižvelgiant į būsenas ir taisyklių rinkinį, įvesties eilutė gali būti priimta arba atmesta. Iš esmės tai yra abstraktus skaitmeninio kompiuterio modelis, kuris nuskaito įvesties eilutę ir keičia jos vidinę būseną, priklausomai nuo esamo įvesties simbolio. Kiekvienas automatas apibrėžia kalbą, t. y. eilučių rinkinį, kurį jis priima. Toliau pateiktame paveikslėlyje parodytos kai kurios esminės bendrojo automatizavimo ypatybės.
Paveikslas: Finite Automata savybės
Aukščiau pateiktame paveikslėlyje parodytos šios automatų savybės:
- Įvestis
- Išvestis
- Automatų būsenos
- Valstybės santykis
- Išvesties santykis
Baigtinis automatas susideda iš šių dalių:
Q : Finite set of states. ? : set of Input Symbols. q : Initial state. F : set of Final States. ? : Transition Function.>
Oficiali mašinos specifikacija yra
{ Q, ?, q, F, ? }> FA skirstomi į du tipus:
1) Deterministiniai baigtiniai automatai (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 tam tikram įvesties simboliui įrenginys pereina tik į vieną būseną. Perėjimo funkcija yra apibrėžta kiekvienoje būsenoje kiekvienam įvesties simboliui. Taip pat DFA nulinis (arba ?) judėjimas neleidžiamas, t. y. DFA negali pakeisti būsenos be jokio įvesties simbolio.
Pavyzdžiui, sukurkite DFA, kuri priima visų eilučių, kurios baigiasi raide „a“, kalbą.
Duota: ? = {a,b}, q = {q0}, F={q1}, Q = {q0, q1}
Pirmiausia apsvarstykite visų galimų priimtinų eilučių kalbų rinkinį, kad sukurtumėte tikslią būsenos perėjimo diagramą.
L = {a, aa, aaa, aaaa, aaaaa, ba, bba, bbba, tėvas, tėvas, tėvas, tėvas}
Aukščiau pateiktas paprastas galimų priimtinų eilučių poaibis, gali būti daug kitų eilučių, kurios baigiasi raide „a“ ir kuriose yra simbolių {a,b}.
1 pav. DFA būsenos perėjimo diagrama su ? = {a, b}
Nepriimamos eilutės yra
ab, bb, aab, abbb ir kt.
Būsenos perėjimo lentelė aukščiau esančiam automatui,
| ?ValstybėSimbolis? | a | b |
|---|---|---|
| q0 | q1 | q0 |
| q1 | q1 | q0 |
Svarbu atkreipti dėmesį į vieną dalyką, modeliui gali būti daug galimų DFA . Paprastai pirmenybė teikiama DFA su minimaliu būsenų skaičiumi.
2) Nedeterministiniai baigtiniai automatai (NFA): NFA yra panaši į DFA, išskyrus šias papildomas funkcijas:
elektroninės bankininkystės apribojimai
- Leidžiamas nulinis (arba ?) judėjimas, t. y. jis gali judėti į priekį neskaitant simbolių.
- Galimybė perduoti į bet kokį skaičių būsenų tam tikrai įvestiei.
Tačiau šios aukščiau pateiktos funkcijos neprideda NFA galios. Jei palyginsime abu pagal galią, abu yra lygiaverčiai.
Dėl minėtų papildomų funkcijų NFA turi skirtingą perėjimo funkciją, likusi dalis yra tokia pati kaip DFA.
?: Transition Function ?: Q X (? U ? ) -->2 ^ Q.>>>Kaip matote iš bet kurios įvesties, įskaitant nulį (arba?), perėjimo funkcija, NFA gali pereiti į bet kokį būsenų skaičių. Pavyzdžiui, žemiau yra NFA aukščiau nurodytai problemai spręsti.
2 pav. NFA būsenos perėjimo diagrama su ? = {a, b}
Būsenos perėjimo lentelė aukščiau nurodytam automatui,
| ?ValstybėSimbolis? | a | b |
|---|---|---|
| q0 | {q0,q1} | q0 |
| q1 | ? | ? |
Svarbu atkreipti dėmesį į vieną dalyką, NFA, jei koks nors įvesties eilutės kelias veda į galutinę būseną, tada įvesties eilutė yra priimtas . Pavyzdžiui, aukščiau pateiktoje NFA yra keli įvesties eilutės 00 keliai. Kadangi vienas iš kelių veda į galutinę būseną, aukščiau nurodyta NFA priima 00.
Kai kurie svarbūs punktai:
- Pateisinimas: