Крайни автомати

Ако някога сте опитвали да напишете вашия бот, преговарящ, интерпретатор на комуникационен протокол и други подобни, вероятно сте се натъквали на държавни машини. Тази тема по принцип не е много трудна, но ако изведнъж не сте имали курс по "теория на автоматите", добре дошли.

Днес ще се опитаме да създадем проста детерминирана машина на състоянието. Изведнъж исках да го напиша на Perl, но тъй като няма да използваме конкретни трикове, няма да е трудно да прехвърлим общата концепция на друг императивен език.

Няма да навлизаме дълбоко в теорията, за това има специална литература, google и wikipedia;). Нека разгледаме самата основа. Нека да видим какво е машина на крайно състояние.

В електрониката и в програмирането в най-простия случай имаме работа с така наречените „превключващи функции“. Това е относително примитивна абстракция, която няма собствена памет: ние сме на входа на аргумент, той е на изхода на определена стойност. Изходната стойност винаги зависи само от входа.

И ако се нуждаем от последващата стойност на функцията, която да зависи от предишната? От няколко предишни? Тук стигаме до известна абстракция със собствената си памет. Това ще е машината. Изходната стойност на машината зависи от стойността на входа и текущото състояние на машината.

Конечен автомат съответно се нарича така, тъй като броят на вътрешните му състояния е краен. И вероятно най-простият от крайните автомати е детерминиран: за всеки входен сигнал има само едно състояние, в което машината може да премине от текущия.

По този начин нашият автомат се определя, както следва:

Първоначално състояние;
въведена азбука (набор от възможни входни сигнали);
много държави;
и таблицата за преход.

Всъщност цялата същност на машината се определя от последния параграф. Преходната таблица (изобразена също като преходна диаграма) се състои от 3 колони: входен сигнал (символ), текущо състояние, следващо състояние. Всичко ще стане ясно с пример.

Базов клас

И така, нека приложим нашия основен клас. Вече решихме, че се нуждаем от начално състояние, текущо състояние и таблица на прехода. Азбуката на въведените символи се определя от проблема, така че ние също трябва да нормализираме (опростим) въвеждането. Изпълнимите методи на низходящия клас ще действат като изходни сигнали. За да опростим живота си, ние изкуствено добавяме символа "*" към азбуката - всеки друг символ.

Предполагам, че имената на всички методи говорят сами за себе си. Може би си струва да се спрем на методите за нормализиране и обработка. Първият преобразува входния низ в хеш, съдържащ полето СИМВОЛ с въведен знак, опростен до автоматичната азбука. И процесът всъщност "часовник" на процесите на преход между състояния, обработка на следващия сигнал.

Нека се опитаме да приложим нещо. Нека това е един вид чат бот.
Нека го основаваме на следните правила:

Преди да изпълните командите, първо трябва да се представите (Влизам)
По команда запомням ще запомним всичко, което потребителят въвежда, завършвайки по команда изход
По команда кажи N изведете наизуст запомнена фраза N
Сесията ще бъде прекратена от командата изход

Така че нека създадем таблица за прескачане за този пример: