Lõpliku oleku masin selgitatud

Lõpliku olekuga masin (FSM) on tarkvara kujundusmuster, kus antud mudel läheb välise sisendi kaudu üle teistesse käitumisolekutesse.

Lõpliku olekumasina mõistmine

Mikroneesia on määratletud selle olekute , algseisundi ja üleminekute järgi .

Mikroneesia võim tuleneb võimest selgelt määratleda erinev käitumine erinevates tingimustes. Tavaliselt kasutatakse Mikroneesia loogeliste käitumisskriptidega, mis hindavad pidevalt hetkeolukorda lingis või sündmustega.

Selle rakendamise pildi kujundamiseks kasutatakse piiratud oleku masina näitena kohvimasinat. Samuti käsitleme Mikroneesia kuvamiseks olekudiagrammi ja pakume kodeerimisnäiteid.

Riigi skeem

Kohvimasina lõpliku oleku masina skeem

See diagramm näitab kolme võimalikku kohvimasina olekut:

  • Avatud
  • ReadyToBuy
  • PoweredOff

Nende olekute vahelised jooned näitavad, millised üleminekud on võimalikud olekute vahel ja mis suunas. Nendel üleminekutel on tingimused, millal Mikroneesia peab riikide vahel muutuma.

  • StartUpMachine Alates olekust PoweredOff kuni olekuni Open peab masin käivituma. Sel juhul tehakse seda käsitsi.
  • sissemakse> = kohvi maksumus Mikroneesia hindab sissemakstud sularaha summat kas silmus või summa muutumisel (soovitatav sellisel juhul). Kui hoiustate kohvimasinasse piisavalt sularaha, liigub Mikroneesia väärtus „Ava” valikule „Valmis”. ".
  • ShutdownMachine Kui tingimus „rohkem kohvi pole enam” on täidetud, läheb seade automaatselt ShutDownMachine-meetodi kaudu funktsioonist Open PoweredOff.
  • DispenseCoffee ReadyToBuy olekus saab kasutaja osta kohvi, mille järel see keedetakse ja väljastatakse. Tingimus on siis, kui BuyCoffee sündmus (! Link vaatleja mustrile!) Käivitub. (skeemil pole näidatud)
  • CancelCoffee Kui kasutaja loobub tühistamisest, läheb seade ReadyToBuy-st Open-i.
  • ShutDownMachine Masin läheb olekusse PoweredOff

Osariikides

Igas olekus on määratletud käitumine, mida teostatakse ainult siis, kui objekt on selles olekus. Näiteks ei keeda kohvimasin PoweredOffi ajal kohvi enne selle sisselülitamist, avatud oleku korral ootab see kas seni, kuni sisestatud on piisavalt sularaha, kuni antakse käsk välja lülitada või kuni kohv saab otsa. Selles avatud olekus saab ta teha selliseid protseduure nagu koristamine, mida teistes riikides ei juhtu.

Esialgne riik

Igal Mikroneesia olekul on algolek, see tähendab, millises olekus see algab, kui see luuakse, ja see tuleb defineerida, kui see on konstrueeritud või instantsitud. Muidugi on tingimuste täitmisel võimalik olekut vahetada.

Üleminekud

Iga riik kas hindab pidevalt, kas see peaks üle minema teisele olekule, või läheb see üle vallandatud sündmuse põhjal.

DFA ja NFA

Lõplikke automaate on kahte tüüpi: deterministlik (DFA) ja mitteterministlik (NFA). Mõlemad aktsepteerivad tavakeeli ja töötavad enam-vähem samal viisil, nagu eespool kirjeldatud, kuid mõningate erinevustega.

DFA aktsepteerib või lükkab tagasi sümbolistringi ja toodab iga sisendstringi jaoks ainult ühe unikaalse arvutuse või automaadi. Deterministlik viitab arvutuse ainulaadsusele. Lõpliku olekuga masinat nimetatakse DFA-ks, kui see järgib järgmisi reegleid:

  1. Iga selle üleminek on ainulaadselt määratud lähte oleku ja sisendsümboliga
  2. Iga oleku ülemineku jaoks on vajalik sisendsümboli lugemine.

NFA ei pea neid piiranguid järgima, see tähendab, et iga DFA on ka NFA. Ja kuna mõlemad tunnevad ära ainult tavakeeli, saab iga NFA teisendada samaväärseks DFA-ks, kasutades PowerSeti algoritmi.

Milliseid reegleid võime oodata NFA-dest, kuid mitte DFA-dest?

  1. NFA-l võib olla tühi stringide üleminek (seda tähistab tavaliselt epsilon). See tähendab, et kui teatud olekus on üleminekureegli jaoks epsilon, saab masin üle minna järgmisse olekusse ilma sisendsümbolit lugemata
  2. NFA-s võib igal oleku- ja üleminekusümboli paaril olla mitu sihtolekut, erinevalt paaride unikaalsetest sihtkohtadest DFA-des
  3. Iga oleku- ja üleminekusümbolipaar loob arvutusharu iga võimaliku sihtkoha jaoks, luues mingisuguse mitmekeermelise süsteemi.
  4. DFA lükkab sisendstringi tagasi, kui see satub mõnele muule olekule kui aktsepteerimisolek. NFA-s vajame stringi aktsepteerimiseks ainult ühte "haru", et maanduda aktsepteerimisolekule.

Kui soovite rohkem teada saada, siis siin on suurepärane põhjalik juhend riigimasinate kohta.