Что относится к конечному автомату

• Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
• Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

Если рассмотреть случай, когда автомат задан следующим образом:

• S — множество стартовых состояний автомата, такое что ;

Тогда появляется третий признак недетерминизма — наличие нескольких начальных (стартовых) состояний у автомата

Конечный автомат с счастливым и грустным Васькой

Конечные автоматы

Для начала дадим определение: конечный автомат (finite-state machine, FSM) — это математическая абстракция, модель, которая может находиться только в одном из конечного числа состояний в каждый конкретный момент времени. Автомат умеет переходить из одного состояния в другое в ответ на данные, которые подаются на вход; изменение состояния называется переходом. FSM определяется списком его состояний, начальным состоянием и инпутами, запускающими переходы.

Вот и всё — у нашего автомата должно быть конечное количество состояний, он находится в одном из них в конкретный момент времени, а ещё у него есть правила, определяющие переход между состояниями. Для наглядности представим кота по имени Васька, который может быть счастливым или грустным. Прямо сейчас Васька счастлив. Когда вы уходите, он грустит, а когда возвращаетесь — снова счастлив. Вы можете возразить, что кошкам наплевать, дома вы или нет, но наш Васька не такой. Вы, наверное, уже видите связь:

• Состояния. Кот либо счастлив, либо грустен и не может испытывать обе эмоции одновременно.
• Начальное состояние. Мы предположили, что Васька по умолчанию счастлив.
• Переходы. Вы можете уйти или прийти, и состояние кота изменится.

Это самый простой пример, который мне удалось придумать. В статье мы обсудим примеры использования подобных автоматов и напишем собственную реализацию с нуля, а также решим пару задач при помощи конечного автомата. Вперёд!

Примеры использования

FSM можно использовать для описания алгоритмов, позволяющих решать те или иные задачи, а также для моделирования практически любого процесса. Несколько примеров:

1. Логика искусственного интеллекта для игр. Вот статья, раскрывающая эту идею.
2. Синтаксический и лексический анализ. Подробнее о таком применении можно прочитать здесь. В том числе сюда относится проверка языка — мы собираемся реализовать её в части статьи, посвящённой проверке бинарного кода.
3. Сложные компоненты. О них есть хорошая статья, однако мы тоже попробуем разобрать эту тему.

Проверка бинарного кода

Создадим наш первый автомат. Посмотрите последний пример по ссылке или пишите код по ходу чтения. Будем реализовывать допускающий автомат с конечным состоянием. Это конечный автомат, цель которого — определить, принадлежит ли некая строка определённому языку, и либо допустить, либо отклонить её. Мы уже обсуждали начальное и другие состояния и переходы, однако теперь потребуется определить ещё два параметра:

• Алфавит. Набор символов, которые должно содержать проверяемое значение (и ни одного символа вне алфавита).
• Конечные состояния. Подмножество существующих состояний — возможно, пустое. Когда FSM завершает свою работу, он принимает проверяемое значение, если это подмножество включает текущее состояние, и отклоняет в противном случае.

• Нам нужно создать автомат для проверки случайных значений, который будет отвечать, является ли значение бинарным кодом.
• Мы принимаем непустые строки с символами 0 и 1 и отклоняем всё остальное.

Вот наш автомат, детерминированный акцептор с конечным состоянием:

У нас получился автомат на основе классов, способный проверять случайные значения на соответствие своим определениям. Чтобы использовать его, мы должны создать экземпляр со всеми необходимыми параметрами. Давайте разберёмся.

• Алфавит. Это очень просто. Мы принимаем только символы 0 и 1.
• Состояния. Это тоже легко. Значение либо бинарное, либо нет. Мы называем состояния q0 («значение — не бинарный код») и q1 («значение — бинарный код»).
• Начальное состояние. Мы не принимаем пустую строку, поэтому начальное состояние — q0.
• Конечные состояния отмечают значение как принятое. В нашем случае единственное подходящее состояние — q1.
• Переходы. См. диаграмму:

Схема акцептора бинарного кода

Помните, что переходы происходят в каждой итерации, и у любого состояния имеются переходы для символов 0 и 1. Это можно интерпретировать так:

• Если текущее состояние — q0, а текущий символ — 0 или 1, выполнить переход в состояние q1.
• Если текущее состояние — q1, а текущий символ — 0 или 1, выполнить переход в то же состояние.
• Если текущий символ не равен 0 или 1, отклонить проверяемое значение независимо от текущего состояния.

Использование и тестирование

Получилось! Обратите внимание: нам не нужно указывать все возможные символы для каждого состояния — когда автомат встречает не прописанный в алфавите символ, он заканчивает работу.

Сложная форма

Пример с проверкой бинарного кода — довольно тривиальный. Вряд ли вам часто придётся решать такие задачи, если придётся вообще. Давайте рассмотрим ещё один пример — создадим форму с несколькими состояниями в UI-ориентированном FSM. Код автомата доступен на CodeSandbox, вы можете перейти к нему или попробовать написать его самостоятельно.

Для начала создайте новый проект в React:

Структура проекта должна выглядеть так:

App.js и index.js не требуют изменений. FSM.js будет содержать новую реализацию FSM, напишем её:

Обратите внимание, что мы удалили алфавит и состояния. Теперь у нас есть только два параметра, которые нужно определить:

• Начальное состояние. Работа FSM должна где-то начинаться.
• Переходы. Объединяем их с состояниями — так мы создаём более ёмкий экземпляр, при этом обеспечивая ту же функциональность.

Наша реализация обязывает использовать метод send для изменения состояния. Мы также добавили метод subscribe . Это очень полезно, если мы хотим, чтобы автомат реагировал на изменение состояния.

Давайте протестируем код на нашем примере с Васькой. Создайте файл test.js :

Теперь запустите его с помощью node test.js (убедитесь, что вы находитесь в каталоге файлов). Вывод на консоли должен выглядеть так:

happy
sad
happy

Автомат определённо работает! Наконец, давайте отреагируем на изменение настроения Васьки:

Запустите автомат снова.

Васька теперь всегда счастлив, потому что мы не бросаем его. Если после перехода состояние — грустное, срабатывает триггер возвращения, и кот снова счастлив.

Похоже, всё работает нормально. Переходим к реальной задаче: создадим анкету с несколькими состояниями, которые нужны для управления интерфейсом. Допустим, мы хотим узнать имя и профессию пользователя. Если пользователь — студент, мы спросим, в каком университете он учится. В противном случае спросим, где он работает. Пользователь может вернуться с этапа Education / Work обратно к этапу Personal, на котором мы спрашиваем имя. Наконец, он может отправить анкету при выборе любого из вариантов занятости.

Небольшая диаграмма, чтобы стало понятнее:

Автомат, определяющий нашу анкету

Когда стало ясно, какие состояния у нас есть и как они соотносятся друг с другом, мы можем приступить к работе над проектом. Первое: нужно установить дополнительные зависимости:

После завершения установки добавляем директорию /components с компонентами внутри. Также мы создаём файл questionnaireMachine.js в директории /src . Теперь структура проекта выглядит так:

Файл questionnaireMachine.js создаёт и экспортирует экземпляр Questionnaire FSM:

Questionnaire FSM

Следующим шагом будет создание презентационного слоя проекта — самой анкеты. Мы разделим его на три отдельных компонента:

• Анкета. Основной компонент, определяющий последовательность вопросов.
• Карточка. Многоразовый компонент для отображения части анкеты.
• Прелоадер. Простая анимированная точка.

Первое: нам нужно подписаться на изменения состояния конечного автомата. Каждый раз, когда состояние меняется, мы обновляем uiState . Это нужно для вычисления свойства active компонента карточки — именно оно позволяет экземпляру компонента карточки решать, показывать себя или нет.

Теперь займёмся компонентом карточки:

Кнопки в нижней части компонента используют указанные действия как listener для события клика. Вот почему мы здесь передаём функции, изменяющие состояние FSM: так компонент анкеты сможет обновить uiState и отобразить нужную карточку.

Последняя мелочь — компонент прелоадера. Здесь нет ничего интересного, просто анимированная точка:

Наконец, добавляем анкету в компонент приложения. Корневой компонент со стилями:

В итоге должно получиться нечто похожее на это. Если да, возрадуйтесь — вы только что создали анкету на основе конечного автомата! Если что-то не работает, сравните свой код с содержимым этой песочнице. У вас наверняка получится наверстать упущенное.

Анкета, которую мы только что создали, разделена на логический и презентационный слои, поэтому при желании её поведение или внешний вид легко скорректировать. Одну реализацию конечного автомата можно использовать в любом числе компонентов — этот подход обеспечивает предсказуемую и стабильную работу приложения.

И ещё кое-что. Несмотря на то, что написать собственный FSM с нуля — очень полезный опыт, для рабочих задач я рекомендую использовать готовые библиотеки, например XState. Там есть и подробная документация, и все необходимые инструменты для работы (их, возможно, даже больше, чем нужно).

Типы конечных автоматов

Автомат — система механизмов, устройств, в которой полностью автоматизированы процессы получения, преобразования, передачи энергии, материалов, информации Термин "автомат" используется в двух аспектах:

При математическом подходе под автоматом понимается математическая модель технического устройства, у которого должны быть входы, внутренние состояния и выходы. Относительно деталей структуры устройства сведений не должно быть.

При техническом подходе под автоматом понимается вполне реальное устройство, например, телефонный автомат, торговый автомат и т. д. В данном случае, естественно, известными являются детали внутреннего строения устройства.

Частным и важным случаем автомата выступает цифровой автомат (ЦА), в котором полностью автоматизированы процессы приема, преобразования, хранения и выдачи цифровой информации.

С точки зрения сигналов ЦА полезно определить как систему, которая может принимать входные сигналы, под их воздействием переходить из одного состояния в другое, сохранять его до прихода следующего входного сигнала, выдавать выходные сигналы.

ЦА считается конечным, если конечны множества входных сигналов X, состояний S и выходных сигналов Y. Конечный автомат можно поставить в соответствие такому устройству, как компьютер. Компьютер перерабатывает поступающие входные данные в выходные данные (результат), но этот результат соответствует не только входным данным, но и текущему состоянию компьютера, т.е. тем данным, которые хранятся в памяти компьютера, например, результаты предыдущих вычислений, программы вычислений.

Работа ЦА осуществляется в автоматном времени, определяемом числом периодов поступления входных сигналов.

Абстрактным автоматом называют математическую модель дискретного устройства, имеющего один входной канал, куда поступают последовательности символов какого-либо языка, один выходной канал, с которого снимают последовательности символов какого-либо другого языка и находящегося в каждый из моментов дискретного времени в каком-либо состоянии. Графически абстрактный автомат представлен рис.

Слова входного языка можно представить символами множества X=1,x₂. x_n>, который называют входным алфавитом, а слова выходного языка — символами множества Y=1,y₂. y_p>, который называют выходным алфавитом. Множество состояний автомата S=1,s₂. s_m> называют алфавитом состояний.

Понятие состояние автомата используется для описания систем, выходные сигналы которых зависят не только от входных сигналов в данный момент времени, но и от некоторой предыстории, т.е. сигналов, которые поступали на входы системы ранее. Следовательно, цифровые автоматы относятся к последовательностным схемам, которые, как уже отмечалось, обладают памятью. Понятие состояние автомата соответствует некоторой памяти о прошлом, поэтому ввод этого понятия позволяет устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входных сигналов.

Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, т.к. каждому интервалу дискретности t будет соответствовать свой выходной сигнал y(t). Следовательно, функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности. В абстрактной теории цифровых автоматов считается, что входные сигналы воздействуют на синхронный автомат в момент начала каждого i-того интервала (кванта) времени, выделенного соответствующим синхроимпульсом (тактом), а изменение внутренних состояний автомата происходит в интервалы времени между смежными синхроимпульсами, когда нет воздействия входных сигналов.

Понятие «состояние» используют для того, чтобы установить функциональную зависимость генерируемых автоматом символов и/или слов выходного языка от символов и/или слов входного языка при реализации автоматом заданного алгоритма. Для каждого состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] на выходе устройства генерируется символ yÎY. Эту зависимость определяет функция выходов автомата j. Для каждого текущего состояния автомата sÎS и для каждого символа xÎX в момент дискретного времени [t] автомат переходит в очередное состояние sÎS. Эту зависимость определяет функция переходов автомата y. Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата (s_1[[1]s₂[2]s₃[3]. ) и последовательности выходных символов (y₁[1]y₂[2]y₃[3]. ), которые для последовательности символов (x₁[1]x₂[2]x₃[3]. ) разворачиваются в моменты дискретного времени t = 1,2,3. В прямоугольных скобках указывают моменты дискретного времени, которые называют иначе тактами, в круглых скобках — последовательности символов алфавитов X, Y и S.

Итак, математическая модель конечного автомата есть трехосновная алгебра, носителями которой являются три множества X, Y и S, а операциями — две функции j и y:

Так как области определения функций переходов и выходов совпадают, то обобщенный оператор поведения автомата можно представить так:

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:

Если на входе автомата имеем слово a = (x₁x₂x₃. x_n), то, считывая последовательно символы этого слова, на выходе автомата генерируется последовательность символов слова b по следующей схеме:

Так как на каждом i-ом такте к слову длины (i-1) приписывается справа очередной символ j(s[1];x₁[1]x₂[2]. x_i[i]), то последовательность символов выходного слова можно записать так:

Если считывание символов входного слова a выполняется последовательно слева направо, то всегда найдется такая последовательность (x₁x₂. x_n-1)=g, для которой

Поэтому если входное слово a = (gx_n), то выходное слово b можно записать так:

Это означает, что последний символ слова b есть результат работы автомата, начавшего работу в состоянии s и считавшего последний символ слова a, но значение этого символа зависит от всей входной последовательности.

Длина выходного слова всегда равна длине входного слова.

Изменение состояний автомата для последовательности символов слова a = (x₁x₂x₃. x_n) может быть описано следующей схемой:

где s[1] — начальное состояние автомата.

Так как за один такт автомат считывает один символ входного слова, то в последовательности состояний автомата можно не указывать номер такта, то есть.

Если входное слово a = (gx_n), то изменение состояния автомата может быть описано так:

Это означает, что s[n+1] есть последнее состояние автомата, начавшего работу в состоянии s и считавшего последний символ слова a в момент дискретного времени n.

Если функции переходов и выходов однозначно определены для каждой пары (s;x)Î(SÄX), то автомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определенным.

Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным.

Если у автомата задано начальное состояние s=s₀ÎS, в котором он находится всегда до приема первого символа входного слова, то автомат называют инициальным. В этом случае модель автомата записывают так:

Последовательность символов в слове b и последовательность состояний автомата s однозначно определяются начальным состоянием автомата s=s₀ и последовательностью символов во входном канале a. Поэтому отображение входного слова a на выходное слово b чаще называют автоматным отображением, то есть b = М(s₀;a), а М – автоматным оператором.

Автоматное отображение обладает свойствами:

1) входное и выходное слова имеют одинаковую длину (свойство сохранения длины);

2) y_i-ый символ выходного слова зависит от всей последовательности символов входного слова, до x_i-го включительно; кроме того если a=a₁a₂, то b=b₁b_2..

Задание конечного автомата:

Для описания (задания) ЦА используются разнообразные средства, называемые языками, которые делятся на начальные и автоматные языки. Поскольку языки базируются на алфавитах, то применительно к ЦА множество Х трактуется в качестве входного алфавита, множество Y — выходного алфавита, а множество S — внутреннего алфавита. Как и для других объектов, для автоматов используются разные таблицы, матрицы, графы.

Наиболее общее при выработке выходных сигналов, формировании новых состояний под действием входных сигналов отражается законом функционирования автомата [4, 12]:

s(t)= d (s(t-1), x(t)),

y(t)= l (s(t-1), x(t)).

Как видно, закон функционирования представляет собой совокупность двух функций: функции перехода d и функции выхода l.

В формулах используются обозначения:

t — данное автоматное время, t-1 — предыдущее автоматное время, d — оператор формирования данного состояния s, l — оператор формирования данного выходного сигнала y, х — входной сигнал.

Видно, что данное состояние s(t) зависит от предыдущего состояния s(t-1) и входного сигнала в данный момент времени, что выходной сигнал в данный момент времени так же определяется предыдущим состоянием и входным сигналом в данный момент времени.

Автомат задан, если заданы:

1. Конечное множество входных сигналов, заданных с помощью входного алфавита X=1, x₂,…, x_m>

2. Конечное множество выходных сигналов, заданных с помощью выходного алфавита y=1, y₂ . y_n>

3. Конечное множество состояний автомата заданного с помощью алфавита S=1,s₂. s_m>

4. Начальное состояние автомата

5. Функция выходов, определяющая зависимость выходного сигнала и состояния автомата y[kt]=f_в(U[kt], a[kt]) где t – длительность такта k – номер такта. Конечный автомат существует в конечном (дискретном) времени.

6. Функция переходов

Функция выходов и функция переходов является характеристическими функциями.

Таким образом, в определении конечного автомата фигурирует три множества и две функции M=в, f_п>

Функция перехода f_п:X*S S Функция выхода f_в:X*S Y

Операторы, описывающие работу автомата, обычно задают таблицей переходов и таблицей выходов.

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

К примеру, рассмотрим таблицы переходов и выходов некоторого автомата.

Таблица переходов автомата

Таблица выходов автомата

В клетку таблицы переходов, находящуюся на пересечении столбца с буквой а_i и строки с буквой x_j, записывается состояние автомата, в которое он переходит из состояния а_i при подаче на вход сигнала x_j. В аналогичную клетку таблицы выходов записывается выходной сигнал y_i, который формируется автоматом при таком переходе.

Операторы переходов и выходов могут быть заданы одной таблицей, по которой однозначно определяются переходы и выходы автомата.

Таблица переходов и выходов автомата

Большую наглядность обеспечивает задание конечных автоматов с помощью графов илидиаграмм состояний.

Граф автомата состоит из узлов, соединенных ветвями. Узлы (кружки на схеме графа) отождествляют внутренние состояния автомата. Каждая ветвь графа, т.е. ориентированная линия, стрелка которой указывает следующее состояние автомата, отмечается входным сигналом, вызывающим в автомате соответствующий данной ветви переход, и выходным сигналом, который возникает при этом переходе. Входной и соответствующий ему выходной сигналы разделяются на чертеже запятой или косой чертой. Если некоторый входной сигнал не меняет состояния автомата, то соответствующая ветвь замыкается на кружке (узле), из которого она выходит.

Поскольку таблица состояний и граф (диаграмма) состояний несут одну и ту же информацию, их можно преобразовать друг в друга. Каждое состояние представляется кружком, а каждый элемент таблицы преобразуется в отрезок ориентированной линии, соединяющей соответствующие кружки. Процедура обратного преобразования очевидна.

Типы конечных автоматов

1) по закону функционирования ЦА делятся на автоматы 1-го рода (автоматы Мили) и ЦА 2-го рода. Последние автоматы в случае, когда нет явной зависимости от входных сигналов x(t), являются автоматами Мура. Видимо, целесообразнее по первому критерию автоматы делить на автоматы Мили и Мура;

В автомате Мили функция выходов j определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата, т.е.

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[t] обнаруживается только при наличии символа во входном канале x[t].

Рис. 1.3. Функциональная схема автомата Мили.

В автомате Мура функция j определяет значение выходного символа только по одному аргументу — состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Математическая модель и схема рекуррентных соотношений автомата Мура имеют вид:

Особенностью автомата Мура является то, что символ y[t] в выходном канале существует все время пока автомат находится в состоянии q[t].

Рис. 1.4. Функциональная схема автомата Мура.

2) по конечности множеств X, Y, и S автоматы бывают конечными и бесконечными. Может быть, данный критерий стоит трактовать как критерий по мощности ЦА;

3) по объему памяти автоматы делятся на автоматы с памятью (последовательностные автоматы) и автоматы без памяти (логические комбинационные схемы);

4) по степени раскрытия структуры автоматы бывают абстрактными автоматами (детали структуры не раскрыты) и структурными автоматами (раскрыты детали структуры);

5) по отношению между автоматами среди автоматов можно выделить подавтоматы, надавтоматы. Если, например, известно, что ЦАА < ЦАВ, то автомат А является подавтоматом автомата В, а автомат В — надавтоматом автомата А;

6) по полноте используемых переходов автоматы делятся на полностью определенные автоматы и частично определенные автоматы;

7) по стабильности периода следования входных сигналов автоматы бывают синхронными автоматами (период следования входных сигналов- постоянная величина) и асинхронными автоматами (период — переменная величина);

8) по вероятности переходов автоматы делятся на детерминированные (не вероятностные) и недетерминированные (вероятностные) автоматы;

9) при нулевой мощности множества внутренних состояний (| S |= 0) автомат называется автономным, при | Y | = 0 — автоматом без выхода. Если среди состояний автомата выделяется начальное состояние s0, то автомат называется инициальным;

10) по применению автоматы можно разделить на автоматы:

а) промышленные (сварочные, кузнечно-прессовые, литейные, строительные, транспортные, упаковочные роботы, контрольные, диагностические и др.);

б) сельскохозяйственные (доильные, раздаточные, уборочные и др.);

в) торговые (газетные, упаковывающие, взвешивающие и др.);

г) учебные (обучающие, тестирующие, моделирующие, демонстрирующие и др.);

д) медицинские (искусственные органы, хирургические, диагностирующие, дыхательные, тренирующие и др.);

е) информационные (видеомагнитофоны, системы "вопрос — ответ" и др.).

Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:

Рис.1. 5. Функциональная схема С-автомата.

Интересно выделить особые классы автоматов, математические модели которых опираются только на два носителя алгебры.

Пусть X=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

Функциональная схема автомата приведена на рис.1.6.

Рис.1.6. Функциональная схема порождающего автомата.

Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата. Такие автоматы называют порождающими или автономными. С помощью такого автомата генерируется последовательность управляющих команд на какие-либо объекты внешней среды.

Пусть Y=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

Функциональная схема автомата приведена на рис.1.7.

Рис. 1.7. Функциональная схема распознающего автомата.

Особенностью функционирования такого автомата является распознавание в последовательности изменений аргумента функции переходов значения (q_i[t];x_i[t]) и перевод автомата в заключительное состояние q_k. С помощью такого автомата обнаруживают заданные возмущения со стороны объектов внешней среды или распознают заданную последовательность входных символов. Поэтому такие автоматы называют распознающими. Часто и автомат Мура представляют автоматом без выхода, так как его выходной сигнал эквивалентен состоянию автомата.

Пусть Q=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

Функциональная схема автомата приведена на рис.8.

Рис. 1.8. Функциональная схема комбинационного автомата.

Особенностью функционирования такого автомата является отсутствие "памяти", т.е. на каждый символ входного алфавита автомат генерирует символ выходного алфавита без учета состояния автомата. Такие автоматы чаще всего называют комбинационными автоматами.

Автоматы, выполняющие роль "0" и

"1" в алгебре автоматов. С — автомат

Любая алгебра должна иметь конструкции, выполняющие в ней роль "0" и "1". По аналогии с алгеброй алгоритмов роль "0" выполняет пустой автомат (ноль-автомат), ЦА0. Пустой автомат – это автомат, в котором запрещены всевозможные переходы. Естественно, что ЦАА \/ ЦА0 = ЦАА, ЦАА /\ ЦА0 = ЦА0.

Роль "1" возлагается на полный ЦА (ЦА1), в простейшем случае такой автомат представляет собой настраиваемое объединение рассматриваемых автоматов. Естественно, что ЦАА \/ ЦА1 = ЦА1, ЦАА /\ ЦА1 = ЦАА, дополнение ЦА1 = ЦА0, дополнение ЦА0 = ЦА1.

Что относится к конечному автомату

Конечный автомат — абстрактная модель, типичный паттерн в разработке компиляторов и не только. Реализовать автомат можно в любом стиле программирования — процедурном, объектно-ориентированном или функциональном.

Что такое автомат?

Будучи абстрактной моделью, автомат в коде или в схемах может стать чем угодно. Ниже показан пример диаграммы состояний для автомата, моделирующего выключатель:

У этого автомата есть:

• два состояния (“свет выключен”, “свет включён”)
• два перехода между этими состояниями
• одно событие “нажали кнопку”, которое вызывает оба перехода
• псевдопереход от чёрного кружка с заливкой, показывающий, какое состояние будет начальным. Конечного состояния здесь нет (иначе оно было бы помечено псевдопереходом к чёрному кружку без заливки)

Чуть более сложный автомат для разбора числа с плавающей точкой показан ниже:

Оба этих автомата являются детерминированными, потому что входной символ или событие однозначно определяет переход, и нет “самопроизвольных” переходов при отсутствии события. Если эти условия не соблюдаются, автомат становится недетерминированным. Также автомат не является детерминированным, если он использует дополнительную память (например, стек ранее накопленных символов) для принятия решения о переходе.

Детерминированный и недетерминированный конечные автоматы

Детерминированный конечный автомат может разобрать строку в один проход из начала в конец, не используя дополнительной памяти кроме заранее заданных таблицы состояний и таблицы переходов между состояниями по событиям. В этой предсказуемости и линейной сложности разбора строки его главное преимущество. Например, в конце разбора строки автомат лексического анализатора приходит в состояние accepted либо в состояние error, что означает успешный или неуспешный разбор строки на токены соответственно.

Любой детерминированный конечный автомат имеет эквивалентное регулярное выражение, и эквивалетный язык регулярной грамматики, и наоборот. По сути это три разных формы представления одной сущности.

Существует формальный алгоритм превращения недетерминированного автомата без дополнительной памяти в детерминированный. Кстати, подобные алгоритмы используют реализации библиотек регулярных выражений: например, для выражения «([a-z])|([a-z]\(\))» легко составить недетерминированный автомат с неоднозначными или пустыми переходами, а алгоритм позволяет превратить его в детерминированный.

Регулярное выражение в ДКА

В промышленных библиотеках регулярных выражений многие операции избыточны и лишь для удобства. Если убрать лишнее и оставить минимум, достаточный для создания произвольных регулярных выражений, то останутся три операции:

• Символ * задаёт итерацию (a.k.a. замыкание Клини)
  • Пример: “1*” ищет строки “”, “1”, “11”, …
  • Пример: “ab” ищет подстроку “ab”, “ab*” ищет подстроки вида “a”, “ab”, “abb”, …

  • Пример: “a

    b

    c

    d” ищут подстроки “a”, “b”, “c”, “d”

  Мы построим детерминированный конечный автомат на основе заданного регулярного выражения. Пусть дано выражение «xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)» , построим для него диаграмму автомата. Для наглядности обозначение начальных и конечных состояний убрано — мы считаем, что любой неожиданный символ переводит в состояние ошибки.

  

  Преобразуем конкатенацию с (x | y*) :

  

  

  

  Получаем промежуточный εНКА, т.е. НКА с “пустыми” — или “самопроизвольными” — переходами:

  

  Убираем переходы по пустой цепочке ε:

  

  Теперь состояния s3 и s5 оказались эквивалентны. Уберём s5, переименуем s6->s5, s7->s6.

  

  Убираем неопределённые переходы из НКА:

  

  Теперь p1 и p5 эквивалентны. Уберём p5, переименуем p6->p5, p7->p6.

  

  Полученный автомат эквивалентен выражению «xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)» .

  • он допускает “aaax”
  • он не допускает “xyyb”

  Применение конечных автоматов

  Существует классификация программ по принципам их работы. Один из вариантов – это классификация Д. Харела, которая делит программы на три вида

  • Трансформирующие системы только трансформируют данные, то есть работают в пакетном режиме
  • Реактивные системы ещё и реагируют на команды или события
  • Интерактивные системы реагируют на команды или события и делают ответное воздействие

  Автоматы применяют в трансформирующих системах, особенно связанных с обработкой текста. Примером подобной системы является интерпретатор, компилятор, шаблонизатор, или же любой простой скрипт для обработки запроса к серверу: