Finite state machine что это
Основы теории вычислительных систем: машина с конечным числом состояний
Теория вычислительных систем — это то, что позволяет нам программировать. Однако, можно писать программы и без представления о концепциях, скрывающихся за вычислительными процессами. Не то, чтобы это было плохо — когда мы программируем, то работаем на намного более высоком уровне абстракции. В конце концов, когда мы ведём машину, то концентрируемся только на двух или трёх педалях, переключателе передач и руле. Для повседневной неспешной езды этого более чем достаточно. Однако, если мы хотим управлять автомобилем на пределе его возможностей, то тут нужно знать гораздо больше, чем просто три педали, КПП и руль.
Такой подход справедлив и в программировании. Большая часть повседневной мирской работы может быть выполнена при минимальном знании теории вычислительных систем или даже вообще без него. Не нужно понимать теорию категорий, чтобы накидать форму «Контакты» в PHP. Тем не менее, если вы планируете писать код, требующий серьёзных вычислений, то тут уж придётся разобраться с тем, что у этих самых вычислений под капотом.
Цель этой статьи — представить некоторые фундаментальные основы вычислений. Если это окажется интересным, то в дальнейшем я могу написать более продвинутый топик на эту тему, но прямо сейчас я хочу просто рассмотреть логику простейшего абстрактного вычислительного устройства — машины с конечным числом состояний (finite state machine).
Машина с конечным числом состояний
Машина с конечным числом состояний (finite state machine, FSM), или конечный автомат (finite automaton) — это математическая абстракция, используемая при проектировании алгоритмов. Говоря простым языком, машина с конечным числом состояний умеет считывать последовательности входных данных. Когда она считывает входной сигнал, то переключается в новое состояние. Куда именно переключится, получив данный сигнал, — заложено в её текущем состоянии. Звучит запутанно, но на самом деле всё очень просто.
Представим устройство, которое читает длинную бумажную ленту. На каждом дюйме этой ленты напечатана буква — a или b.
Как только устройство считывает букву, оно меняет своё состояние. Вот очень простой граф переходов для такой машины:
Кружки — это состояния, в которых машина может быть. Стрелочки — переходы между ними. Так что, если вы находитесь в состоянии s и считываете a, то вам необходимо перейти в состояние q. А если b, то просто остаётесь на месте.
Итак, если изначально мы находимся в состоянии s и начинаем читать ленту из первого рисунка слева направо, то сначала будет прочитана a, и мы переместимся в состояние q, затем b — вернёмся обратно в s. Следующая b оставит нас на месте, а a вновь переместит в q. Элементарно, но какой в этом смысл?
Оказывается, если пропустить ленту с буквами через FSM, то по её итоговому состоянию можно сделать некоторые выводы о последовательности букв. Для приведённго выше простого конечного автомата финальное состояние s означает, что лента закончилась буквой b. Если же мы закончили в состоянии q, то последней на ленте была буква a.
Это может показаться бессмысленным, но существует масса задач, которые можно решить с помощью такого подхода. Простейший пример: определить, содержит ли HTML-страница следующие теги в заданном порядке:
Также конечный автомат может использоваться для представления механизмов парковочного счётчика, автомата с газировкой, автоматизированного газового насоса и тому подобных штук.
Детерминированная машина с конечным числом состояний (Deterministic Finite State Machine)
Машины с конечным числом состояний, которые мы рассматривали выше, являются детерминированными. У них из любого состояния существует только один переход для любого разрешённого входного сигнала. Другими словами, не существует двух различных путей из данного состояния, когда вы считываете, допустим, букву a. На первый взгляд такое ограничение кажется глупым.
Недетерминированная машина с конечным числом состояний (Nondeterministic Finite State Machine)
Итак, надо распознать букву a с последующим нулём или более одинаковых букв b или c и с замыкающей следующей буквой алфавита. Самый простой способ отобразить этот алгоритм с помощью машины с конечным числом состояний представлен ниже. Финальное состояние t означает, что строка была принята целиком и соответствует шаблону.
На этом принципе основан алгоритм большинства шахматных программ. Они просматривают все возможности всех возможных ходов на данном этапе и выбирают ту стратегию, которая в данный момент даёт максимальное преимущество над противником.
Регулярные выражения
Если вы когда-нибудь занимались любым видом программирования, то вы почти наверняка сталкивались с регулярными выражениями (regular expressions). Регулярные выражения и машины с конечным числом состояний функционально эквивалентны. Всё, что можно допустить для (или связать с) регулярным выражением, можно допустить для (или связать с) конечным автоматом. Например, шаблон, который мы разбирали выше, можно связать с
Это положение известно как лемма о накачке для регулярных языков. Её основная мысль: если ваш шаблон имеет блок, который может быть повторён более, чем один раз, то этот шаблон не является регулярным. Другими словами, ни регулярные выражения, ни машины с конечным числом состояний не могут быть сконструированы так, чтобы распознавать все строки, которые можно связать с шаблоном.
Машина Тьюринга
Так как же нам распознавать нерегулярные шаблоны? Существует теоретическое устройство, подобное конечному автомату и называемое машиной Тьюринга (Turing Machine). Как и у машины с конечным числом состояний, у него имеется бумажная лента, с которой оно считывает информацию. Однако, машина Тьюринга также способна записывать и стирать данные на ленте. Полное объяснение принципов этого устройства займёт больше места, чем у нас здесь имеется, поэтому я обозначу лишь несколько важных моментов, относящихся к нашей дискуссии о машинах с конечным числом состояний и регулярных выражениях.
Машина Тьюринга вычислительно полна, и всё, что в принципе может быть вычислено, может быть вычислено с помощью машины Тьюринга. А благодаря способности записывать данные на ленту с такой же лёгкостью, как и считывать их с ленты, она не ограничена конечным числом состояний. Бумажную ленту можно представить, как имеющую бесконечную длину. Очевидно, что современные компьютеры не обладают бесконечным количеством памяти, однако, они имеют её достаточно, чтобы вы не вышли за предел для тех типов задач, которые они способны обработать.
Машина Тьюринга предоставляет нам воображаемое механическое устройство, позволяющее визуализировать и понять, как работает вычислительный процесс. Это особенно полезно для понимания пределов вычислений. Если это интересно, то в будущем я могу написать отдельную статью о машине Тьюринга.
Почему это имеет значение?
Понимание, что машины с конечным числом состояний и регулярные выражения функционально эквивалентны, открывает невероятно интересные способы применения движков регэкспов. Особенно, когда дело доходит до создания бизнес-правил, которые могут быть изменены без перекомпиляции всей системы.
Знание основ теории вычислительных систем позволяет вам брать проблему X, которую вы понятия не имеете как решать, и применять к ней подход: «Я не знаю, как решить X, но я знаю, как решить Y и как привести решение для Y к решению для X. Вот почему теперь я знаю, как решить X».
Простые стейт-машины на службе у разработчика
Представьте на минутку обычного программиста. Допустим, его зовут Вася и ему нужно сделать анимированную менюшку на сайт/десктоп приложение/мобильный апп. Знаете, которые выезжают сверху вниз, как меню у окна Windows или меню с яблочком у OS X. Вот такое.
Начинает он с одного выпадающего окошка, тестирует анимацию, выставляет ease out 100% и наслаждается полученным результатом. Но вскоре он понимает, что для того, чтобы управлять менюшкой, хорошо бы знать закрыто оно сейчас или нет. Мы-то с вами тут программисты опытные, все понимаем, что нужно добавить флаг. Не вопрос, флаг есть.
Вроде, работает. Но, если быстро кликать по кнопке, меню начинает моргать, открываясь и закрываясь не успев доанимироваться в конечное состояние. Вася добавляет флаг animating. Теперь код у нас такой:
Через какое-то время Васе говорят, что меню может быть полностью выключено и неактивно. Не вопрос! Мы-то с вами тут программисты опытные, все понимаем, что… нужно добавить ЕЩЕ ОДИН ФЛАГ! И, всего-то через пару дней разработки, код меню уже пестрит двустрочными IF-ами типа вот такого:
Вася начинает задаваться вопросами: как вообще может быть, что animating == true и enabled == false; почему у него время от времени все глючит; как тут вообще поймешь в каком состоянии находится меню. Ага! Состояния. О них дальше и пойдет речь.
Знакомьтесь, это Вася.
Состояние
Вася уже начинает понимать, что многие комбинации флагов не имеют смысла, а остальные можно легко описать парой слов, например: Disabled, Idle, Animating, Opened. Все мы тут программисты опытные, сразу вспоминаем про state machines. Но, для Васи придется рассказать что это и зачем. Простым языком, без всяких математических терминов.
У нас есть объект, например, вышеупомянутая менюшка. Объект всегда находится в каком-то одном состоянии и реагируя на различные события может между этими состояниями переходить. Обычно состояния, события и переходы удобно описывать вот такими схемами (кружочками обозначены начальное и конечные состояния):
Из схемы понятно, что из состояния Inactive в Active можно попасть только по событию Begin, а из состояния Paused можно попасть как и в Active, так и в Inactive. Такую простую концепцию почему-то называют «Конечный Автомат» или «Finite State Machine», что очень пугает обычных людей.
По завету ООП, состояния должны быть скрыты внутри объекта и просто так снаружи не доступны. Например, у объекта во время работы может быть 20 разных состояний, но внешнее API на вопрос «чо как дела?» отвечает «ничо так» на 19 из них и только на 1 ругается матом, что проср*ли все полимеры.
Следуя концепции стейт машин, очень легко структурировать код так, что всегда будет ясно что и как делает тот или иной объект. Всегда будет понятно, что что-то пошло не так, если система вдруг попыталась перейти в недоступное из данного состояния состояние. А события, которые вдруг посмели прийти в неправильное время, можно смело игнорировать и не бояться, что что-нибудь сломается.
Самая простая в мире стейт машина
Допустим, теперь Вася делает проект на C# и ему нужна простая стейт машина для одного типа объектов. Он пишет что-то типа такого:
А вот так обрабатывает события в зависимости от текущего состояния:
Но, мы-то с вами тут программисты опытные, все понимаем, что метод setState в итоге разрастется на пару десятков страниц, что (как написано в учебниках) не есть хорошо.
State Pattern
Погуглив пару часов, Вася решает, что State Pattern идеально подходит в данной ситуации. Тем более, что старшие программисты все время соревнуются кто больше паттернов запихнет в свой апп, так что, решает Вася, паттерны это дело важное.
Например, для State Pattern можно сделать интерфейс IState:
И по отдельному классу для каждого состояния, которые этот интерфейс имплементят. В теории выглядит красиво и 100% по учебнику.
Но, во-первых, для каждой несчастной мелкой стейт машины нужно городить уйму классов, что само по себе небыстро. Во-вторых, рано или поздно начнутся проблемы с доступом к общим данным. Где их хранить? В основном классе? А как классы-состояния получат к ним доступ? А как мне тут за 15 минут перед дедлайном впилить быстро мелкий хак в обход правил? И подобные проблемы взаимодействия, которые будут сильно тормозить разработку.
Реализация на основе особенностей языка
Некоторые языки программирования облегчают решение тех или иных задач. В Ruby, например, так вообще есть целый DSL (и не один) для создания конечных автоматов. А в C# конечный автомат можно упростить через Reflection. Вот как-то так:
Реализовав систему описанную выше, Вася понимает, что у нее тоже больше минусов, чем плюсов:
Фреймворк
А тем временем, Вася уже вовсю стал вникать в теорию стейт машин и решил, что хорошо бы иметь возможность формально их описывать через API или (о Боже) через XML, что в теории звучит круто. Мы-то с вами тут программисты опытные, все понимаем, что нужно писать свой фреймворк. Потому что другие не подходят, так как у всех у них есть один фатальный недостаток.
Вася решил, что с помощью его фреймворка можно будет быстро и легко создать стейт машину без необходимости писать много ненужного кода. Фреймворк не будет накладывать никаких ограничений на разработчика. Все вокруг будут веселы и жизнерадостны.
Я попробовал множество фреймворков на разных языках, несколько подобных написал сам. И всегда для описания конечного автомата средствами фреймворка требовалось больше кода, чем в простом примере. Все они накладывают те или иные ограничения, а многие пытаются делать сразу столько всего, что для того, чтобы разобраться, как же тут все-таки создать несложную стейт машину, приходится продолжительное время рыться в документации.
Вот, например, описание конечного автомата фреймворком stateless:
Но, пробившись через создание стейт машины, можно воспользоваться полезными функциями, которые предоставляет фреймворк. В основном это: проверка правильности переходов, синхронизация зависимых стейт машин и суб-стейт машин и всяческая защита от дурака.
XML — это отдельное зло. Кто-то когда-то придумал использовать его для написания конфигов. Стадо леммингов java разработчиков длительное время молилось на него. А теперь никто уже и не знает зачем все используют XML, но продолжают бить всех, кто пытается от него избавиться.
Вася тоже загорелся идеей, что можно все сконфигурировать в XML и НЕ ПИСАТЬ НИ СТРОЧКИ КОДА! В итоге в его фреймворке отдельно лежат XML файлы примерно такого содержания:
Класс! И никакого программирования. Но, мы-то с вами тут программисты опытные, все понимаем, что программирование никуда не ушло. Вася заменил кусок императивного кода на кусок декларативного кода, добавив при этом во фреймворк интерпретатор XML, который все еще в пару раз усложнил. А потом попробуй это отдебажить, когда код на разных языках и разбросан по проекту.
Соглашение
И тут Васе все это надоело и он вернулся обратно к самому простому в мире конечному автомату. Он его немного переделал и придумал правила как писать в нем код.
UPDATE: спасибо за комментарии. Здесь действительно не хватало небольшого объяснения.
У нас есть несколько состояний. Переход между ними — это транзакция из атомарных операций, то есть они все происходят всегда вместе, в правильном порядке и между ними не может вклиниться еще какой-то код. При смене состояния с A на B происходит следующее: выполняется код выхода из состояния A, состояние меняется с A на B, выполняется код входа в состояние B.
Для перехода на состояние A нужно вызвать метод stateA, который выполнит нужную логику и вызовет setState(A). Самому вызывать setState(A) крайне не рекомендуется.
UPDATE: В setState() пишется уникальная логика выхода из состояния, а в stateB() возможна специфическая логика выхода из состояния A при переходе в B. Но очень редко используется.
Простое соглашение для написания стейт машин. Оно достаточно гибкое и имеет следующие плюсы:
Как и во всех соглашениях, какой-то код может сперва находиться в одном месте, но потом у него появится другой смысл, или окажется, что он где-то дублируется. Тогда мы можем его перенести в другое место. Никто нам не запрещает. Все-таки код не вытесан из камня, это всего лишь текст, который (о ужас!) можно и нужно менять с развитием проекта.
UPDATE: а setState() вполне можно заменить одним сеттером для наглядности.
Заключение
На этом заканчивается увлекательное приключение Васи в мире стейт машин. А ведь впереди еще столько всего интересного. Отдельного топика бы только заслужили параллельные и зависимые стейт машины.
Я надеюсь, что, если вы еще не используете стейт машины повсеместно, эта статья перетянет вас на сторону добра; если вы пишите свой уберфреймворк для работы со стейт машинами, она поможет свежим взглядом посмотреть на то, что у вас получается.
Я надеюсь, что эта статья поможет разработчикам задуматься где и когда стоит использовать паттерны и фреймворки, и что описанное соглашение по оформлению стейт машин окажется кому-то полезным.
Конечные автоматы в реальной жизни: где мы их используем и почему
Привет, меня зовут Антон Субботин, я выпускник курса «Мидл фронтенд-разработчик» в Яндекс.Практикуме. Не так давно мы с наставником курса Захаром Овчаровым провели вебинар, посвящённый конечным автоматам и их практическому применению. Вебинар получился интересным, а потому по его следам я написал статью для Medium на английском языке. Также есть запись вебинара. Однако мы с Захаром решили сделать ещё кое-что: перевести на русский и немного расширить статью, чтобы вы могли никуда не ходить и прочитать её здесь, на Хабре. Разобрались с предысторией — теперь начнём погружение в мир конечных автоматов.
Конечный автомат с счастливым и грустным Васькой
Конечные автоматы
Для начала дадим определение: конечный автомат (finite-state machine, FSM) — это математическая абстракция, модель, которая может находиться только в одном из конечного числа состояний в каждый конкретный момент времени. Автомат умеет переходить из одного состояния в другое в ответ на данные, которые подаются на вход; изменение состояния называется переходом. FSM определяется списком его состояний, начальным состоянием и инпутами, запускающими переходы.
Вот и всё — у нашего автомата должно быть конечное количество состояний, он находится в одном из них в конкретный момент времени, а ещё у него есть правила, определяющие переход между состояниями. Для наглядности представим кота по имени Васька, который может быть счастливым или грустным. Прямо сейчас Васька счастлив. Когда вы уходите, он грустит, а когда возвращаетесь — снова счастлив. Вы можете возразить, что кошкам наплевать, дома вы или нет, но наш Васька не такой. Вы, наверное, уже видите связь:
Это самый простой пример, который мне удалось придумать. В статье мы обсудим примеры использования подобных автоматов и напишем собственную реализацию с нуля, а также решим пару задач при помощи конечного автомата. Вперёд!
Примеры использования
FSM можно использовать для описания алгоритмов, позволяющих решать те или иные задачи, а также для моделирования практически любого процесса. Несколько примеров:
Проверка бинарного кода
Создадим наш первый автомат. Посмотрите последний пример по ссылке или пишите код по ходу чтения. Будем реализовывать допускающий автомат с конечным состоянием. Это конечный автомат, цель которого — определить, принадлежит ли некая строка определённому языку, и либо допустить, либо отклонить её. Мы уже обсуждали начальное и другие состояния и переходы, однако теперь потребуется определить ещё два параметра:
Вот наш автомат, детерминированный акцептор с конечным состоянием:
У нас получился автомат на основе классов, способный проверять случайные значения на соответствие своим определениям. Чтобы использовать его, мы должны создать экземпляр со всеми необходимыми параметрами. Давайте разберёмся.
Схема акцептора бинарного кода
Помните, что переходы происходят в каждой итерации, и у любого состояния имеются переходы для символов 0 и 1. Это можно интерпретировать так:
Использование и тестирование
Получилось! Обратите внимание: нам не нужно указывать все возможные символы для каждого состояния — когда автомат встречает не прописанный в алфавите символ, он заканчивает работу.
Сложная форма
Пример с проверкой бинарного кода — довольно тривиальный. Вряд ли вам часто придётся решать такие задачи, если придётся вообще. Давайте рассмотрим ещё один пример — создадим форму с несколькими состояниями в UI-ориентированном FSM. Код автомата доступен на CodeSandbox, вы можете перейти к нему или попробовать написать его самостоятельно.
Для начала создайте новый проект в React:
Структура проекта должна выглядеть так:
App.js и index.js не требуют изменений. FSM.js будет содержать новую реализацию FSM, напишем её:
Обратите внимание, что мы удалили алфавит и состояния. Теперь у нас есть только два параметра, которые нужно определить:
Давайте протестируем код на нашем примере с Васькой. Создайте файл test.js :
Теперь запустите его с помощью node test.js (убедитесь, что вы находитесь в каталоге файлов). Вывод на консоли должен выглядеть так:
Автомат определённо работает! Наконец, давайте отреагируем на изменение настроения Васьки:
Запустите автомат снова.
Васька теперь всегда счастлив, потому что мы не бросаем его. Если после перехода состояние — грустное, срабатывает триггер возвращения, и кот снова счастлив.
Похоже, всё работает нормально. Переходим к реальной задаче: создадим анкету с несколькими состояниями, которые нужны для управления интерфейсом. Допустим, мы хотим узнать имя и профессию пользователя. Если пользователь — студент, мы спросим, в каком университете он учится. В противном случае спросим, где он работает. Пользователь может вернуться с этапа Education / Work обратно к этапу Personal, на котором мы спрашиваем имя. Наконец, он может отправить анкету при выборе любого из вариантов занятости.
Небольшая диаграмма, чтобы стало понятнее:
Автомат, определяющий нашу анкету
Когда стало ясно, какие состояния у нас есть и как они соотносятся друг с другом, мы можем приступить к работе над проектом. Первое: нужно установить дополнительные зависимости:
Файл questionnaireMachine.js создаёт и экспортирует экземпляр Questionnaire FSM:
Questionnaire FSM
Следующим шагом будет создание презентационного слоя проекта — самой анкеты. Мы разделим его на три отдельных компонента:
Теперь займёмся компонентом карточки:
Кнопки в нижней части компонента используют указанные действия как listener для события клика. Вот почему мы здесь передаём функции, изменяющие состояние FSM: так компонент анкеты сможет обновить uiState и отобразить нужную карточку.
Последняя мелочь — компонент прелоадера. Здесь нет ничего интересного, просто анимированная точка:
Наконец, добавляем анкету в компонент приложения. Корневой компонент со стилями:
В итоге должно получиться нечто похожее на это. Если да, возрадуйтесь — вы только что создали анкету на основе конечного автомата! Если что-то не работает, сравните свой код с содержимым этой песочнице. У вас наверняка получится наверстать упущенное.
Анкета, которую мы только что создали, разделена на логический и презентационный слои, поэтому при желании её поведение или внешний вид легко скорректировать. Одну реализацию конечного автомата можно использовать в любом числе компонентов — этот подход обеспечивает предсказуемую и стабильную работу приложения.
И ещё кое-что. Несмотря на то, что написать собственный FSM с нуля — очень полезный опыт, для рабочих задач я рекомендую использовать готовые библиотеки, например XState. Там есть и подробная документация, и все необходимые инструменты для работы (их, возможно, даже больше, чем нужно).
Самые простые конечные автоматы или стейт-машины в три шага
Привет, Хабр!
Перейдем сразу к делу, но небольшая предыистория все таки нужна: полтора года назад возникла необходимость реализовать простую стейт — машину (конечный автомат), владея теорией с университета, я был уверен в тривиальности данной задачи (все мы оптимисты).
Время, проведенное с google, прошло без результатов, так как существующие решения не только имели фатальный недостаток, но и ряд других серьезных недочетов, таких как сложная структура и отсутствие документации.
Вскоре я наткнулся на эту статью, которая подтвердила отсутствие удобных решений.
Что сделал тогда?
Так как задачу требовалось решить быстро (ну как обычно), то мой конечный автомат был реализован с помощью словарей, то есть:
Таким образом, в нужном месте функция «издает сигнал» и, в зависимости от текущего состояния и сигнала, происходит переход (устанавливается следующее состояние)
Но что дальше?
Это был третий курс обучения в университете по специальности «Программная инженерия» и было уже пора определиться с темой диплома. Посовещавшись с предполагаемым научным руководителем, возникла идея того, что хорошо бы не только написать библиотеку для реализации конечных автоматов, но и как-то визуально их представлять.
Решение: библиотека и графический редактор.
Подробнее о реализации каждого из них расскажу в следующих статьях, а пока что покажу что получилось.
Спустя год разработки.
Графический редактор
Реализован на wpf с использованием ReactiveUI.
Тут у нас структура конечного автомата в виде графа и в виде таблицы переходов.
Накидываем узлы, соединяем их и сохраняем в xml файл.
В целом я постарался сделать удобно и стильно, а как бонус — куча горячих клавиш поддерживается. Ссылку на репозиторий с документацией в виде gif прикреплю в конце.
Возможности
Две темы
Два представления конечного автомата:
Валидация
Добавление узлов и соединений
Отмена действий
Сворачивание и перемещение узлов
Масштабирование
Выделение элементов
Наименования для состояний и переходов
Перемещение переходов
Удаление переходов
Импорт/Экспорт из/в xml
Сохранение схемы в PNG/JPEG
Библиотека
Реализуем конечный автомат в три шага:
Отмечу, что необязательно использовать редактор, ведь конечный автомат можно описать в коде и, если понадобиться, сделать export схемы, которую потом уже открыть в редакторе.
А что с переходами?
Для перехода внутри функции, которая обрабатывает Entry/Exit в состояние, вызываем:
Переход не произойдет сразу же, просто указанный переход будет помечен как следующий, то есть сначала отработают все события состояния, а потом уже будет вызван переход.
Что есть ещё?
Полный список фич и подробную документацию можно найти в репозитории, ссылку тоже оставлю.
Возможности:
Будущее проекта
Диплом был защищен на отлично, но забрасывать проект не хотелось бы.
Поэтому буду рад помощи с реализацией нижеописанных пунктов.
Также, если Вы нашли ошибки или у вас есть другие идеи — пишите, буду очень рад!
Библиотека. Возможные улучшения:
Последний пункт распишу подробнее. Сейчас пользователю необходимо помнить, какие имя у переходов и состояний описаны внутри файла.
И работа с ними происходит так:
Сразу скажу, что dynamic не подойдет так как все равно нужно помнить название.
Тут наверное нужна какая-то кодо-генерация, но решение пока что не нашел.
Графический редактор. Возможные улучшения:
Выводы
Ссылки
Графический редактор, исходники на GitHub: SimpleStateMachineNodeEditor
Библиотека, исходники на GitHub: SimpleStateMachineLibrary