Обяснена машина за крайно състояние

Крайният автомат (FSM) е модел на софтуерно проектиране, при който даден модел преминава към други състояния на поведение чрез външен вход.

Разбиране на крайната автомат

FSM се дефинира от своите състояния , първоначалното си състояние и преходите .

Силата на FSM идва от способността да се дефинират ясно различни поведения при различни условия. Обикновено FSM се използва с цикли за поведенчески скриптове, които постоянно оценяват текущата ситуация в цикъл или със събития.

За да ви помогне да оформите изображение как това може да се приложи, кафемашина ще бъде използвана като пример за машина с крайно състояние. Също така ще покрием диаграма на състоянието, за да визуализираме FSM и ще предоставим примери за кодиране.

Диаграма на състоянието

Диаграма на машината за крайно състояние на кафе машина

Тази диаграма показва три възможни състояния за кафе машината:

  • Отворете
  • ReadyToBuy
  • PoweredOff

Линиите между тези състояния показват кои преходи са възможни между състоянията и в коя посока. Тези преходи имат условия, когато FSM трябва да се промени между държавите.

  • StartUpMachine От състояние PoweredOff до състояние Open машината трябва да се стартира. В този случай това се прави ръчно.
  • депозит> = цена на кафе FSM оценява сумата на депозираните пари в цикъл или когато сумата се променя (препоръчва се в този случай) Ако депозирате достатъчно пари в кафе машината, FSM ще премине от „Open“ в „ReadyToBuy ".
  • ShutdownMachine Машината автоматично ще премине от Open към PoweredOff чрез метода ShutDownMachine, ако е изпълнено условието „няма останали кафета“.
  • DispenseCoffee В състояние ReadyToBuy потребителят може да си купи кафе, след което то ще бъде приготвено и дозирано. Условието е, когато събитието BuyCoffee (! Връзка към модел на наблюдател!) Се задейства. (не е показано на диаграмата)
  • CancelCoffee Ако потребителят реши да отмени, устройството ще премине от ReadyToBuy към Open.
  • ShutDownMachine Устройството ще премине в състояние PoweredOff

Държави

Във всяко състояние има дефинирано поведение, което ще бъде изпълнено само когато обектът е в това състояние. Например, по време на PoweredOff кафемашината няма да приготвя кафе, преди да се включи, по време на отвореното състояние ще изчака или докато има вкарани достатъчно пари, докато не се даде команда за изключване, или докато свърши кафето. По време на това отворено състояние той може да прави рутинни операции като почистване, което няма да се случи в други състояния.

Първоначално състояние

Всеки FSM има начално състояние, това означава в кое състояние той започва, когато е създаден и трябва да бъде дефиниран, когато е конструиран или създаден. Разбира се възможно е директно да се промени състоянието, ако са изпълнени условията.

Преходи

Всяко състояние или постоянно преценява дали трябва да премине в друго състояние, или ще премине в друго състояние въз основа на задействано събитие.

DFA и NFA

Има два типа крайни автомати, детерминистичен (DFA) и недетерминиран (NFA). И двамата приемат редовни езици и работят горе-долу по същия начин, описан по-горе, но с някои разлики.

DFA приема или отхвърля низ от символи и създава само едно уникално изчисление или автомат за всеки входен низ. Детерминистичният се отнася до уникалността на изчислението. Краен автомат се нарича DFA, ако се подчинява на следните правила:

  1. Всеки от неговите преходи се определя уникално от състоянието на източника и входящия символ
  2. Четенето на входен символ се изисква за всеки преход на състоянието.

NFA не трябва да се подчинява на тези ограничения, което означава, че всеки DFA е и NFA. И тъй като и двамата разпознават само обикновени езици, всеки NFA може да бъде преобразуван в еквивалентен DFA, използвайки алгоритъма за изграждане на powerset.

И така, какви правила можем да очакваме да намерим в NFA, но не и DFA?

  1. NFA може да има празен преход на низ (обикновено се обозначава с ипсилон). Означава, че когато е в определено състояние с епсилон за правило за преход, машината може да премине в следващото състояние, без да чете входен символ
  2. В NFA всяка двойка състояние и символ на преход може да има множество състояния на дестинация, за разлика от уникалните дестинации на двойки в DFA
  3. Всяка двойка символ на състояние и преход създава „клон“ на изчисление за всяка от възможните си дестинации, създавайки някаква многонишкова система.
  4. DFA ще отхвърли входния низ, ако попадне в друго състояние, различно от състоянието на приемане. В NFA ни е необходим само един „клон“, който да кацне в състояние на приемане, за да приемем низа.

Ако искате да научите повече, ето страхотно задълбочено ръководство за държавни машини.