Что такое конечный автомат
Конечные автоматы
Введение
Конечные автоматы являются мощным инструментом для работы. Компиляторы работает на основе конечных автоматов. Любой алгоритм которые вы пишете может быть представлен в виде конечного автомата.
В конечном автомате количесто состояний конечно, а результат его работа определяется по его конченому состоянию (Wikipedia).
Существует несколько видов конечных автоматов:
Детерминированный кончечный автомат (ДКА)
Из любого состояние должен быть только один преход по символову, иначе этот автомат недерминирован.
ДКА является самым удобным из всех конченых автоматов. Его удобнее всего обработаывать, всегда стараются свести задачу к построению ДКА. Но разобрать НКА и ε-НКА также необходимо.
Недетерминированный конечный автомат(НКА)
Предположим нам надо построить автомат, который принимает все строки, состоящие из символов [0, 1], где второй символ будет 0.
ε-Недетерминированный конечный автомат (ε-НКА)
ε-НКА очень похож на НКА, только теперь мы можем преходить по ε. Теперь ничего не считав, мы сможем перейти из одной вершины в другую.
Принмает теже слова, что и предыдущий
Эквиалетность
Есть свойство у конченых автоматов — это их эквиалетность. ДКА НКА ε-НКА. Благодаря этому мы можем спокойно из ε-НКА сделать ДКА, это нам сильно пригодится.
Вкратце, разобрав какие бывают автоматы, мы можем перейти к более подробному изучению их реализации
Реализация
Обработка автомата
Как же можно проверить принимает ли данный кончечный автомат строку.
Для ДКА все очевидно. Мы храним матрицу преходов, текущее состояние (когда мы ничего не считали, тек. сотояние = начальное состояние) и терминальные вершины. Считываем по одному символу, и переходим в состояние по матрице перехода.
Для НКА вместо текущего состояния мы храним множество текущих состояний. Разберем НКА данный выше.
Пусть мы хотим перейти по символу 0. Текущее множество состояний — множество, состоящее из одной вершины — начальной. У нас есть два прехода по символу 0 => множество состояний у нас будет
Обработка ε-НКА похожа на обработку НКА. Предположим наше текущее множество S. Перед считываением следущего символа: для всех q ∈ S добавить в множество S вершину достигаемую из q по символу ε.
Детерминация автомата
Перевести автомат из ДКА в НКА легко. Нам просто ничего не нужно делать, т.к. ДКА это обобщенный случай НКА.
Но что делать если мы хотим превести из ε-НКА в ДКА (НКА является обобшенным случаем ε-НКА). Этот процесс называется детерминацией автомата.
Начнем обоходить наш ε-НКА, например, DFS-ом. Вершиной графа является множество текущих состояний. Состояниями нового ДКА будут все вершины графа. При переходе к новой веришне мы выбираем символ по которому хотим перейти, и добавляем этот переход. Приведу псевдокод DFS-a для большой ясности:
Если в множестве есть терминальное состояние, то состояние нового ДКА будет тоже терминальным.
К сожалению число состояние нового ДКА будет расти экспоненциально, что не очень хорошо, т.к. это будет потреблять много памяти.
Алгоритм минимизации ДКА
Любой ДКА имеет эквиалетный ему ДКА с минимальным числом состояний. Как его «сжать»? Заметим, что неразличимые вершины мы можем соединить в одну.
Что такое различимое состояние?
Состояние p и q являются различимыми, если есть такое слово s, что преходя из вершины p по слову s мы попадаем в терминальное состояние, а из вершины q в не-терминальное, или наоборот.
1) Терминальное и не-терминальное состояние являются различимыми. Перейдем по пустому слову и окажемся в двух различимых состояниях.
2) Состояния a и b различимы. Если существуют состояния c и d, и из c есть переход по символу x в состояние a, а из веришны d есть переход по символу x в состояние b, то состояние a и b различимы.
Мы нашли все различимые состояния. Теперь нам надо «схлопнуть» все неразличимые.
Регулярные выражения
Регулярные варжения напрямую связаны с конечными автоматами. Введем некоторые обозначения:
∅ — пустое множество.
ε — строка, которая не сожержит символов.
Пусть A и B регулярные выражения. L(A) и L(B) — кончечные языки, которые данные регулярные варжения задают.
Это основные операции прменимые к регулярным варжением. Можно всетрить и другие, но все они могут быть представлены операциями данными выше.
Вот представление основных операций регулярных выражений в виде ε-НКА.
Дале разбираем это выражение рекурсивным спуском и строим ε-НКА.
Чтобы обработать Регулярное выражение построим для ε-НКА, а потом получим из ε-НКА ДКА, который очень легко обрабатывать.
Конечный автомат (он же машина состояний) на чистом С
Почти каждый микроконтроллерщик сталкивался с громадными switch-case и мучительно их отлаживал.
И много кто, начиная писать реализацию какого-либо протокола, задумывался как написать её красиво, изящно, так чтобы через месяц было понятно что ты имел в виду, чтобы она не отжирала всю память и вообще какала бабочками.
И вот тут на помощь приходят машины состояний, они же конечные автоматы (те самые которые используются в регулярных выражениях).
Собственно через регулярные выражения я к ним и пришёл.
Недавно мне потребовалось реализовать несложную функциональность устройства с 4-мя кнопками — выделение в потенциально хаотичных нажатиях кнопок двух кодовых последовательностей и выполнение определённых действий, когда последовательность найдена.
Поясню на примере: есть 4 кнопки — A, B, C, D и кодовая последовательность ACDA. Тогда при последовательном нажатии B, C, A, D, A, C, D, A, B, устройство должно зажечь лампочку после 8-го (предпоследнего) нажатия. С точки зрения регулярных выражений задача проста — ищем во входной строке подстроку «ACDA». Как только нашли — зажигаем лампочку. Но тащить в микроконтроллер какую-нибудь библиотеку по работе с regexp не хотелось. Я чувствовал что всё можно сделать самому и проще. Тогда я решил попробовать самостоятельно реализовать конечный автомат соответствующий поиску данной подпоследовательности.
А теперь — немного теории и практики:
Основная черта конечных автоматов — они описываются набором возможных состояний, набором сигналов (событий) и таблицей переходов. Таблица переходов — это сопоставление паре из текущего состояния и пришедшего сигнала нового состояния.
Представим, что у нас есть автомат с 3 состояниями и 3 сигналами, которые нужно обрабатывать. По приходу каждого сигнала автомат совершает переходит в новое состояние.
Очевидно что данный код не очень удобочитаем и будет катастрофически разрастаться с увеличением количества состояний и сигналов.
Кроме того, если мы захотим в каждый переход добавить какое-либо однотипное действие (например логирование — что-то вроде ), то это породит кучу изменений в коде. При редактировании таких изменений почти наверняка будет допущена какая-нибудь ошибка и отладка превратится в ад.
Заметим, что суть двух вложенных switch — это выбор из таблицы (по колонке и по столбцу) и вспомним что формально конечные автоматы удобно записывать в виде таблицы переходов где каждая строка соответствует сигналу, каждый столбец — состоянию, а на пересечении записано состояние в которое переходит автомат.
Попробуем упростить имеющийся код, задав таблицу переходов, извините за тафтологию, таблицей.
Продемонстрированый вид инициализации даннных известен как designated inits и был введён в С99.
теперь надо полученную структуру данных обработать — пишем функцию doFSM_table:
Чтобы сделать получившийся автомат ещё более универсальным и придать ему возможность совершать какие-то действия кроме перехода по состояниям добавим в таблицу указатели на функции-обработчики, соответствующие переходам:
Вообще улучшать данный механизм можно долго, но данная статья ставит своей целью не разработать универсальную библиотеку для реализации конечных автоматов, а продемонстрировать как некоторые задачи могут быть решены значительно проще и компактнее чем «в лоб», при этом не прибегая ни к каким замысловатым библиотекам или языкам.
В заключение приведу таблицу, получившуюся для задача поиска подпоследовательности, с которой я начинал:
Создаем Конечный Автомат на PHP
Что такое Конечный Автомат?
Я объясню на примере. Предположим, что я хочу купить молоко, тогда такая задача будет иметь примерно следующие состояния:
Произведение оплаты за молоко
Поездка обратно домой
Везде. В большинстве (если не во всех) бизнес-процессах, требующих как минимум двух «состояний». Например: службы доставки, операции купли-продажи, процесс найма и т.д.
Внимание! если вы новичок или опыт с ООП мал тогда не воспринимайте статью как руководство к действию. Конечные Автоматы не популярны коммерческой разработке и могут быть полезны в проектах, которые направлены на транзакции, например платёжные шлюзы. Задумываются о них лишь когда запутанность транзакций превышает все мыслимые пределы.
Зачем мне нужен Конечный Автомат?
Вернемся назад к примеру с молоком. Зачем мне нужно создавать конечный автомат, в котором процесс идет от А до Я?. Загвоздка в том что всегда что-то случается, могут возникнуть ошибки, недоразумения или проблемы.
Таким образом состояния для нас теперь следующие:
Произведение оплаты за молоко
Поездка обратно домой
Можно даже добавить больше состояний, но для нашего исследования тут хватит основных. Также возможно сжатие состояний и использование меньшего их количества, например «состояние отмены поездки» и «состояние отмены покупки молока» можно объединить просто в «Отмена».
Как автоматизировать процесс?
milk = 0 нет молока, milk = 1 у меня есть молоко
money = кол-во денег в кармане
price = цена молока
stock_milk = количество молока в магазине
store_open = 0 магазин закрыт, = 1 открыт
gas = бензин моей машины
Так мы можем сформировать состояния и переходы:
Состояние после перехода
Когда возможен переход?
Поездка за молоком
Когда milk = 0 и gas > 0
Отмена поездки (это конец процесса)
store_open = 1 и stock_milk > 0
store_open = 0 или stock_milk = 0
Произведение оплаты за молоко
(это также увеличивает milk +1)
неверно, а money (видим пробелы) правильно.
Пятая, и, наконец, мы объединим все это вместе.
Тестирование с использованием пользовательского интерфейса
Если конфигурация верна, то на странице должен отображаться новый экран.
Теперь давайте создадим новую задачу. Давайте начнем с начальными значениями: milk = 0, money = 999 и gas = 10 и нажмем на кнопку «Create a new job«. Теперь задача была создана и перешла из состояния «Вождение автомобиля»(1) в состояние » Купить молоко»(2).
Давайте установим следующие значения, store_open=1 и stock_milk=1 и нажмем на кнопку Set field values (она установит новые значения и проверит все условия).
Замечания и предложения
Теория вычислений. Введение в конечные автоматы
Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рассуждения и легкость программной или аппаратной реализации.
С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.
У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.
Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.
Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ ‘a’, из состояния 1 в состояние 2, если символ ‘b’.
Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.
Стартовое состояние — состояние откуда КА начинает свою работу.
Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.
Детерминированные конечные автоматы (deterministic finite automaton)
Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.
Детерминированность — для всех состояний имеется максимум и минимум одно правило для любого возможного входного символа, то есть например, для состояния 1 не может быть два перехода с одним и тем же входным символом.
Недетерминированные конечные автоматы (nondeterministic finite automaton)
НКА не является каким-то существенным улучшением ДКА, просто в нем добавлен так сказать синтаксический сахар, в виде свободных переходов, недетерминированности и множеств состояний. Реализовать можно как массив состоящий из структур в которой хранится состояние, входной символ и следующее состояние.
Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.
Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.
Множества состояний — в один момент времени НКА может находится в нескольких состояниях.
Заключительное состояние обозначается двойным кругом.
В стартовом состоянии у нас текущим состоянием является <1>, при входном символе ‘b’ у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа ‘b’ текущим состоянием является множество <1, 2>.
Свободным переходом обозначается пунктирной линией.
Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии <2, 4>.
Для преобразования НКА в ДКА используется алгоритм Томпсона.
При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.
Конечные автоматы с магазинной памятью (pushdown automaton)
Это тот же КА, но с дополнительной памятью в виде стека. Теперь для совершения перехода нужно учитывать еще несколько факторов, символ который нужно удалить из стека и символы которые нужно добавить в стек.
КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стека (я понимаю, что память тоже конечна).
Удаление символа из стека — при любом переходе решается какой символ вытолкнуть, если на вершине стека не оказалось такого символа, то он и не выталкивается. Так же если символ нужно оставить в стеке, то он добавляется вместе с добавляемыми символами.
Добавление символов в стек — при любом переходе решает какие символы добавить в стек.
Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.
ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.
Машина Тьюринга (Turing machine)
Самая мощная машина из существующих, его преимущество перед другими в ленте с которой он может работать как хочет. В нем нет свободных переходов. Умеет интерпретировать другие автоматы такие как КА, КАМП.
Лента — это одномерный массив в который могут записываться данные за счет головки над ячейкой, который можно заранее заполнить входными данными.
Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются ‘_’.
Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.
ДМТ эквивалентен НМТ, так, что они тоже не различаются.
Универсальная машина Тьюринга (universal Turing machine)
Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.
Конечные автоматы в реальной жизни: где мы их используем и почему
Привет, меня зовут Антон Субботин, я выпускник курса «Мидл фронтенд-разработчик» в Яндекс.Практикуме. Не так давно мы с наставником курса Захаром Овчаровым провели вебинар, посвящённый конечным автоматам и их практическому применению. Вебинар получился интересным, а потому по его следам я написал статью для 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. Там есть и подробная документация, и все необходимые инструменты для работы (их, возможно, даже больше, чем нужно).