Пояснення кінцевого автомата

Кінцевий автомат (FSM) - це шаблон дизайну програмного забезпечення, коли дана модель переходить в інші поведінкові стани за допомогою зовнішнього введення.

Розуміння скінченної машини

FSM визначається своїми станами , початковим станом та переходами .

Сила FSM походить від здатності чітко визначати різні способи поведінки в різних умовах. Зазвичай FSM використовується з циклами поведінкових сценаріїв, які постійно оцінюють поточну ситуацію в циклі або з подіями.

Щоб допомогти сформувати уявлення про те, як це можна застосувати, кавоварка буде використана як приклад кінцевого автомата. Ми також розглянемо діаграму стану для візуалізації FSM та надамо приклади кодування.

Діаграма стану

Діаграма кавового автомата з кінцевим станом

На цій схемі показано три можливі стани для кавової машини:

  • відчинено
  • ReadyToBuy
  • PoweredOff

Лінії між цими станами показують, які переходи можливі між станами і в якому напрямку. Ці переходи мають умови для того, коли FSM повинен змінюватися між штатами.

  • StartUpMachine Від стану PoweredOff до стану Відкриття машина повинна запуститися. У цьому випадку це робиться вручну.
  • депозит> = вартість кави FSM оцінює кількість внесених готівкових коштів або у циклі, або коли сума змінюється (рекомендується в цьому випадку) Якщо ви внесете достатньо готівки в кавову машину, FSM перейде з "Відкрити" на "ReadyToBuy '.
  • ShutdownMachine Машина автоматично перейде з відкритого режиму на 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 за допомогою алгоритму побудови потужності.

Тож які правила ми можемо очікувати у NFA, але не DFA?

  1. NFA може мати перехід порожнього рядка (зазвичай позначається епсилоном). Це означає, що, перебуваючи в певному стані з епсилоном для правила переходу, машина може перейти в наступний стан, не зчитуючи вхідний символ
  2. У NFA кожна пара символів стану та переходу може мати кілька станів призначення, на відміну від унікальних цільових призначень пар у DFA
  3. Кожна пара символів стану та переходу створює "гілку" обчислень для кожного з можливих пунктів призначення, створюючи якусь багатопотокову систему.
  4. DFA відхилить вхідний рядок, якщо він потрапить у будь-який стан, відмінний від стану прийняття. У NFA нам потрібна лише одна "гілка", яка потрапляє в стан прийняття, щоб прийняти рядок.

Якщо ви хочете дізнатись більше, тут є чудовий поглиблений посібник про державні машини.