Алгоритмизация и Программирование

Морозов Владимир Игоревич

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

Обработка последовательностей

Частой задачей в вычислительной технике является обработка некоторых последовательностей
Мы уже рассмотрели сортировку, поиск и т.п.
Но последовательности могут содержать не только неокторые сравнимые объекты, но также, например, действия пользователя
В таких случаях важно понять, является ли заданная последовательность «действий» корректной для конкретного исполнителя

Пример

Пусть у нас есть примитивный калькулятор
Он может работать только с натуральными числами и поддерживает только операции $+$, $-$, $*$, $/$
Для получения решения пользователь должен ввести $=$

Корректность ввода

Для такого калькулятора легко определить, является ли тот или иной ввод пользователя корректным
Например, "$11+25=$" — корректное выражение, "$123/1025=$" — тоже
Тогда как "$11=$", "$25++2$", "$+/33$" и "$=371+$" очевидно некорректны

Реализация

Для программной реализации проверки корректности (например, в качестве предварительного этапа перед расчётом) необходимо ответить на два вопроса
Во-первых, как реализовать проверку всех допустимых выражений, если их, очевидно, бесконечное множество?
Во-вторых, как описать множество всех корректных выражений?
Далее мы увидим, что эти два вопроса эквивалентны

Решение

Ответом на оба вопроса являются конечные автоматы
Конечный автомат — особый способ организации алгоритма вычислений
Во-первых, конечный автомат читает выражение символ за символом
Во-вторых, на каждом шаге работы автомат ожидает ввода некоторого корректного символа

Пример

К примеру, если было прочитано $115$, ожидается знак арифметической операции или ещё одна цифра
Если же было прочитано $1+2$, ожидается $=$ или ещё одна цифра
Если автомат читает «неожиданный» символ, констатируется некорректность выражения
Например, если прочитано $33$, автомат «не ожидает» $=$ в качестве следующего символа

Задача построения автомата

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

Задача построения автомата

Однако такое ограничение не позволяет нам отличать, например, ситуации, где прочитано $125$ и $125+55$
Чтобы учесть подобные различия, вводится понятие состояния конечного автомата
Тогда набор «ожидаемых» символов определяется последним прочитанным символом и текущим состоянием автомата

Смена состояний

Изначально автомат находится в начальном состоянии
Прочитав «ожидаемый» символ, автомат переходит в другое состояние (возможно, в то же самое) в зависимовтси от символа
Для каждого состояния определяется набор ожидаемых символов, а также следующее состояние, в которое перейдёт автомат, прочитав каждый из символов

Пример

Например, автомат для нашего калькулятора в начальном состоянии будет ожидать цифру $0..9$
Прочитав цифру, автомат перейдёт в новое состояние
В новом состоянии автомат будет ожидать цифру $0..9$ или арифметический оператор
Прочитав цифру, автомат останется в том же состоянии, а прочитав оператор, перейдёт в новое и т.д.

Графическое представление конечного автомата

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

Конечный автомат для калькулятора

Состояния

Состояние $q_0$ называется начальным, это точка входа
Состояние $q_3$ — конечное или принимающее
Когда автомат достигает конечного состояния, считав при этом всю строку, это значит, что строка принята

Замечание

Автомат не обязательно останавливает работу при достижении конечного состояния
Из конечного состояния также могут быть переходы в другие состояния
Главное — быть в конечном состоянии, когда строка закончится

Ещё один пример

Чтобы закрепить знания о графическом представлении автоматов, построим ещё один
На этот раз автомат должен принимать все арифметические равенства с целыми числами (не проверяя верность)
Например, $-22 + 11 = -555$ должно быть принято

Конечный автомат для целочисленных равенств

Формализация

Теперь дадим формальное определение детерминированного конечного автомата $M$. Он состоит из:

Множества всех состояний $Q$
Начального состояния $q_0 \in Q$
Множества конечных (допускающих) состояний $A \subseteq Q$
Алфавита символов входной строки $\Sigma$

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

Наконец, последней и наиболее интересной составляющей конечного автоамта является функция переходов $\delta$
Именно она определяет, какие символы «ожидаются» в каждом из состояний, и в какое состояние автомат переходит при чтении символа

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

Функция переходов принимает текущее состояние и текущий считанный символ
Возвращает она состояние, в которое автомат должен перейти
Задаётся функция переходов перечислением её значений для всех допустимых аргументов

Пример функции переходов

Приведём пример функции переходов для калькулятора

$\delta(q_0, 0..9) = q_1$

$\delta(q_1, 0..9) = q_1$

$\delta(q_1, \{+, -, *, /\}) = q_2$

$\delta(q_2, 0..9) = q_2$

$\delta(q_2, =) = q_3$

Замечание

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

Табличное представление

$q_i \backslash \Sigma_j$	$0$	$1$	$2$	$3$	$...$	$+$	$-$	$*$	$/$	$=$
$q_0$	$q_1$	$q_1$	$q_1$	$q_1$	$...$	-	-	-	-	-
$q_1$	$q_1$	$q_1$	$q_1$	$q_1$	$...$	$q_2$	$q_2$	$q_2$	$q_2$	-
$q_2$	$q_2$	$q_2$	$q_2$	$q_2$	$...$	-	-	-	-	$q_3$

Определение

Итак, детерминированный конечный автомат представлен следующей пятёркой:
Автомат начинает работу в начальном состоянии и работает, пока не закончится строка или не встретится «неожиданный» символ
Если в конце работы автомата он находится в конечном состоянии, строка принимается

Конфигурация автомата

Дадим более формальное определение корректной и некорректной строке для данного автомата
Для этого сначала необходимо ввести понятие конфигурации автомата
Конфигурация — пара $C = (q, w)$ из текущего состояния $q$ и текущего непрочитанного остатка строки $w$
Конфигурация автомата полностью описывает конкретный этап его работы

Выводимость

Теперь введём отношение выводимости на данном автомате $M$
Конфигурация $C'$ выводима (достижима) из конфигурации $C$, если, находясь в конфигурации $C$, автомат может сделать ряд шагов и прийти в конфигурацию $C'$
Выводимость в автомате $M$ обозначается как

Определение корректной строки

Пусть даны строка $w$ и автомат $M$
Строка $w$ корректна (принимается
автоматом $M$), если:
где $\epsilon$ — пустая строка

Формальные языки

Пусть даны алфавит $\Sigma$ и автомат $M$
Определим множество всех строк (любой длины), которые можно составить из символов алфавита $\Sigma$ как $\Sigma^*$
Тогда $L \subseteq \Sigma^*$ называется языком, определяемым автоматом $M$, если:

Применение

Концепция конечного автомата (или машины состояний — state machine) нашла широкое применение в вычислительной технике
Мы рассмотрим применение конечного автомата на уже знакомой задаче поиска подстроки в строке

Поиск подстроки

Идея состоит в построении конечного автомата по подстроке и обработке строки с помощью этого автомата
Т.к. автомат читает по символу на каждом шаге и никогда не возвращается назад, сложность этапа поиска — $\Theta(N)$

Наивное решение

Осталось разработать алгоритм, который будет эффективно строить конечный автомат из искомой подстроки
Простейшим решением было бы построить автомат с одним переходом на каждый символ подстроки
На рисунке пример для подстроки $abc$

Недостатки

Применять такой автомат можно, передавая ему на каждом шаге строку, укороченную на $1$ символ
Если автомат дойдёт до конечного состояния, подстрока найдена
Однако сложность такого решения равна сложности простого скользящего окна с шагом $1$

Идея оптимизации

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

Оптимизация

Представим, что, используя простейший ДКА, мы нашли очередное вхождение подстроки, т.е. автомат находится в конечном состоянии
К какому состоянию нужно перейти, чтобы не перезапускать работу автомата, а продолжить обработку строки?

Пример

Решение

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

Дальнейшая оптимизация

Во всех случаях, когда в строке встречается буква, которой нет в подстроке, автомат должен переходить в начальное состояние
Для экономии места это не будет отражаться на рисунках

Усложнение

Рассмотрим более сложную ситуацию
Пусть есть строка $ababab...$ и подстрока $ababc$
Куда нужно совершить переход при чтении следующего символа на рисунке?

Какой переход верен?

Решение

В состояние $q_1$ перейти нельзя, т.к. пропустим совпадение, если следующий символ строки равен $c$
Попробуем обобщить данную ситуацию

Обобщение

Пусть $k$ символов строки совпали с символами подстроки
Тогда мы находимся в состоянии $q_k$ и на вход автомата идёт следующий символ строки $t_i$
Нам нужно «сдвинуть» подстроку так, чтобы длиннейший её префикс совпадал со строкой $s_{0..k}t_i$

Вычисление сдвига

В терминах конечного автомата это аналогично переходу к состоянию $q_i$, где $j$ — длина такого префикса
Для вычисления длин подобных префиксов существует суффикс-функция $\sigma_s: \Sigma^* \rightarrow \mathbb{N}_0$

Суффикс-функция

Суффикс функция похожа на остальные функции предобработки строк, которые мы уже рассматривали
Для каждой строки $x$ суффикс-функция возвращает длину наибольшего префикса подстроки $s$, являющегося суффиксом этой строки

Вычисление

В нашем случае строки $x$ строятся по форме $s_{0..k}t_i$, где $s_{0..k}$ — префикс подстроки $s$ длины $k$, а $t_i$ — очередной символ подстроки $t$
Тогда для быстрого получения значений суффикс-функции нужно хранить таблицу размером $m |\Sigma|$
Построить такую таблицу можно с использованием префикс- или $Z$-функции

Результат

Таким образом, функция перехода конечного автомата для поиска подстроки в строке дополняется следующим образом

$$\delta(q_j, t_i) = q_{\sigma_s(s_{0..j}t_i)}$$

Результат

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

$$\forall t_i \in \Sigma, j = \overline{0..M}: \delta(q_j, t_i) = q_{\sigma_s(s_{0..j}t_i)}$$ $$\forall j = \overline{1..M}: \delta(q_{j-1}, s_j) = q_j$$

Результат

Результирующий конечный автомат с данной функцией перехода будет выглядеть следующим образом (переходы в состояние $q_0$ не изображены)

Другие применения конечных автоматов

Как уже было отмечено, конечные автоматы имеют множество применений
Ещё одно из них — регулярные выражения
В действительности для регулярных выражений строятся более сложные конечные автоматы (недетерминированные)
Однако в данной лекции мы ограничимся упрощённым вариантом

Упрощение

Мы рассмотрим упрощённый аналог регулярных выражений — глобы (globs)
Это специальные выражения, которые используются командными оболочками (например, bash) для выполнения команд над группами файлов
К примеру, чтобы скопировать все текстовые файлы в папку folder, в bash можно написать


                            cp *.txt folder

Обработка глобов

В действительности при обработке глобов ДКА не используются
Однако теоретически нет никаких препятствий такой реализации
Символ $*$ означает любое количество любых символов ($0$ или больше)
Символ $?$ означает ровно один любой символ

Пример

Попробуем построить конечный автомат, соответствующий выражению *.t?t

Обсуждение

Наш автомат примет строки file.txt, aaa.tst, 0123.tat и т.д.
Однако этой функциональности недостаточно
Выражение *.t?t соответствует также строкам file.tat.tot.txt, abc.tbt.tct и т.п.
Но наш автомат не принимает такие строки

Модификация

Модифицируем наш автомат, чтобы он корректно принимал все строки, соответствующие выражению *.t?t

Полезные источники

RU Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание. Раздел 32.3. – Основная книга нашего курса.
RU А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. — Очень подробный разбор с математическими выводами.
EN Статья о реализации регулярных выражений в различных ЯП

Полезные источники

EN Пример конечного автомата с лекции, доступный для изменения
EN Пример другого конечного автомата с лекции, доступный для изменения