Galutinės būsenos mašina paaiškinta

Galutinės būsenos mašina (FSM) yra programinės įrangos projektavimo modelis, kai nurodytas modelis per išorinį įėjimą pereina į kitas elgesio būsenas.

Suprasti baigtinės būsenos mašiną

FMV apibrėžia jo būsenos , pradinė būsena ir perėjimai .

FMV galia kyla iš gebėjimo aiškiai apibrėžti skirtingą elgesį skirtingomis sąlygomis. Paprastai FMV naudojamas su kilpiniais elgesio scenarijais, kurie nuolat vertina esamą situaciją cikle ar su įvykiais.

Kad susidarytų vaizdas, kaip tai gali būti taikoma, kavos aparatas bus naudojamas kaip baigtinio aparato pavyzdys. Mes taip pat apimsime būsenos schemą, norėdami vizualizuoti FMV ir pateikti kodavimo pavyzdžius.

Valstybės schema

Kavos aparato baigtinės būsenos aparato schema

Ši schema rodo tris galimas kavos aparato būsenas:

  • Atviras
  • „ReadyToBuy“
  • Išjungta

Linijos tarp šių būsenų parodo, kokie perėjimai tarp būsenų galimi ir kuria kryptimi. Šie perėjimai turi sąlygas, kada FMV turi keistis tarp valstybių.

  • StartUpMachine Nuo „PoweredOff“ būsenos iki „Open“ būsenos mašina turi būti paleista. Šiuo atveju tai daroma rankiniu būdu.
  • depozitas> = kavos kaina FMV įvertina įneštų grynųjų sumą per ciklą arba pasikeitus sumai (šiuo atveju rekomenduojama). Jei į kavos aparatą įnešite pakankamai pinigų, FMV nuo „Atidaryta“ pereis į „ReadyToBuy“ ".
  • „ShutdownMachine“ Mašina automatiškai pereis iš „Open“ į „PoweredOff“ naudodama „ShutDownMachine“ metodą, jei tenkinama sąlyga „nebėra kavos“.
  • DispenseCoffee „ReadyToBuy“ būsenoje vartotojas gali nusipirkti kavos, po kurios ji bus išvirta ir išleista. Sąlyga yra tada, kai „BuyCoffee“ įvykis (! Susiekite su stebėtojų modeliu!) Suveiks. (nenurodyta diagramoje)
  • „CancelCoffee“ Jei vartotojas nusprendžia atšaukti, aparatas pereis iš „ReadyToBuy“ į „Open“.
  • ShutDownMachine Mašina pereis į „PoweredOff“ būseną

Valstybes

Kiekvienoje būsenoje yra apibrėžtas elgesys, kuris bus vykdomas tik tada, kai objektas yra toje būsenoje. Pvz., „PoweredOff“ metu kavos aparatas negers kavos, kol jis nebus įjungtas, „Open“ būsenos metu jis lauks, kol bus įdėta pakankamai grynųjų, kol bus suteikta išjungimo komanda, arba kol baigsis kava. Per šią „Open State“ būseną ji gali atlikti tokias procedūras kaip valymas, kurios neįvyks kitose valstybėse.

Pradinė būsena

Kiekvienas FMV turi pradinę būseną, tai reiškia, kurioje būsenoje jis prasideda, kai jis yra sukurtas, ir turi būti apibrėžtas, kai jis yra sukonstruotas ar sukurtas. Žinoma, galima tiesiogiai pakeisti būseną, jei tenkinamos sąlygos.

Perėjimai

Kiekviena valstybė arba nuolat vertina, ar ji turėtų pereiti į kitą būseną, arba pereis į kitą būseną pagal sukeltą įvykį.

DFA ir NFA

Yra dviejų tipų baigtiniai automatai: deterministinis (DFA) ir nedeterministinis (NFA). Abi jos priima įprastas kalbas ir veikia daugmaž taip pat, kaip aprašyta aukščiau, tačiau turi tam tikrų skirtumų.

DFA priima arba atmeta simbolių eilutę ir kiekvienai įvesties eilutei sukuria tik vieną unikalų skaičiavimą ar automatą. Deterministinis reiškia skaičiavimo unikalumą. Galutinės būsenos mašina vadinama DFA, jei ji laikosi šių taisyklių:

  1. Kiekvieną jo perėjimą unikaliai lemia jo šaltinio būsena ir įvesties simbolis
  2. Kiekvienam būsenos perėjimui reikia perskaityti įvesties simbolį.

NFA neprivalo laikytis šių apribojimų, o tai reiškia, kad kiekvienas DFA taip pat yra NFA. Kadangi jie abu atpažįsta tik įprastas kalbas, kiekvieną NFA galima konvertuoti į lygiavertį DFA naudojant PowerSet konstrukcijos algoritmą.

Taigi kokias taisykles galime tikėtis rasti NFA, bet ne DFA?

  1. NFA gali turėti tuščią eilutės perėjimą (paprastai žymimą epsilonu). Tai reiškia, kad esant tam tikrai būsenai su „epsilon“ perėjimo taisyklei, mašina gali pereiti į kitą būseną neskaitydama įvesties simbolio
  2. NFA kiekviena būsenos ir perėjimo simbolių pora gali turėti kelias paskirties būsenas, o ne unikalias porų paskirties vietas DFA
  3. Kiekviena būsenos ir perėjimo simbolių pora sukuria skaičiavimo „šaką“ kiekvienam galimai paskirties vietai, sukurdama tam tikrą daugiasriegę sistemą.
  4. DFA atmes įvesties eilutę, jei ji pateks į bet kurią valstybę, išskyrus priėmimo būseną. NFA mums reikia tik vieno „filialo“ nusileisti priėmimo būsenoje, kad galėtume priimti eilutę.

Jei norite sužinoti daugiau, pateikite puikų išsamų valstybės mašinų vadovą.