Applications of Finite State Machines
LVEE 2019
In this presentation we define the finite state automata (FSA), Moore and Mealy machines, and Finite State Transducers. Weighted and stochastic finite state machines are described. Also, a few well-known and custom algorithms based on finite state machines, are described.
В настоящей презентации приводятся определения допускающего конечного автомата, автоматов Мура и Мили, а также конечно-автоматных преобразователей. Также даются определения взвешенных конечных автоматов и приводятся примеры задач, как классических, так и нестандартных, решаемых с их помощью.
Abstract licensed under Creative Commons Attribution-ShareAlike 3.0 license
Редактировать | Diff | Назад
Алексей,
сильно ждем финальную версию тезисов!
%%%begin-myprojects
\documentclass{article}
\usepackage{ucs}
\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
%\usepackage{fancyvrb}
%\usepackage{relsize}
%\usepackage{graphicx}
%%\usepackage[]{algorithm2e}
%%\usepackage{algorithmicx}
%%\usepackage[ruled]{algorithm2e}
\usepackage[ruled,vlined]{algorithm2e}
%\usepackage{subfig}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage[russian]{babel}
%\usepackage{lmodern}
%\setbeamertemplate{navigation symbols}{}
%\usetheme{Boadilla}
%\usetheme{CambridgeUS}
%\usetheme{Malmoe}
%\usetheme{Singapore}
%\usetheme{boxes}
%\usecolortheme{crane}
%\usecolortheme{dove}
%\usecolortheme{seagull} % very cool with \usetheme{default}
%\usefonttheme{professionalfonts}
%\useinnertheme{rectangles}
%\mode
\title{Применение аппарата конечных автоматов}
\author{Чеусов Алексей \textless\texttt{vle@gmx.net}\textgreater}
\date{Минск, Беларусь, 2019}
\begin{document}
\maketitle
Аппарат конечных автоматов -- один из базовых и наиболее важных
понятий в информатике и программировании. Конечные автоматы изучаются
во всех без исключения университетах и институтах по специальностям,
так или иначе связанным с информатикой и программированием. Тем не
менее, по моему мнению недостаточное внимание в нашей системе
образования уделяется практическому их применению, что, на моей
взгляд, негативно сказывается на уровне подготовке отечественных
программистов. Данным докладом хотелось бы хотя бы частично
ликвидировать это досадную ситцацию, и пробудить интерес к во
многом забытым конечным автоматам. С этой целью будут приведены
примеры практических задач, реашемых с их помощью.
Прежде всего хочется сказать, что данная статья является дополнением
к презентации, доступной на сайте \mbox{\texttt{http://lvee.org}} или по ссылке\\
\mbox{\texttt{http://www.mova.org/\textasciitilde{}cheusov/pub/lvee/2019/fsa\_presentation.pdf}}.
Начать следует с определений и теорем, хорошо знакомых любому
выпускнику ВУЗ-а по технической специальности.
\textbf{Определение:} Недетерминированным конечным автоматом (НКА) называется пятерка
\mbox{$$}, где
\begin{itemize}
\item $I$ -- конечное непустое множество символов (алфавит);
\item $S$ -- конечное непустое множество состояний;
\item $Q$ -- множество стартовых состояний, $Q \subseteq S$;
\item $F$ -- множество конечных состояний, $F \subseteq S$;
\item $\delta$ -- отношение переходов $\delta \subseteq S \times I \times S$
(или, иначе, $\delta: S \times I \rightarrow 2^S$).
\end{itemize}
Языком КА является множество различных последовательностей символов алфавита, допускаемых
конечным автоматом, т.е., цепочек символов вдоль пути от стартового до конечного состояния КА.
\textbf{Определение:} Регулярный язык над алфавитом $\Sigma$ определяется следующим образом:
\begin{itemize}
\item Пустой язык $\emptyset$ и язык $\{\epsilon\}$, состоящий из пустой строки, является регулярным языком;
\item $\{a\}$, где $a \in \Sigma$, является регулярным языком;
\item Если $A$ и $B$ регулярные языки, то $A \cup B$ (объединение), $A \bullet B$ (конкатенация),
и $A\ast$ (звезда Клини) являются регулярными языками;
\item Никакие другие языки над $\Sigma$ не являются регулярными.
\end{itemize}
Этот формализм дает нам так называемые ``регулярные выражения''.
\textbf{Определение:} Детерминированным конечным автоматом (ДКА) является пятерка $$, где
\begin{itemize}
\item $I$ -- конечное непустое множество символов (алфавит);
\item $S$ -- конечное непустое множество состояний;
\item $q$ -- стартовое состояние, $q \in S$.
\item $F$ -- множество конечных состояний, $F \subseteq S$.
\item $\delta$ -- функция переходов: $\delta: S \times I \rightarrow S$
\end{itemize}
\textbf{Теоремы}:
\begin{itemize}
\item НКА и ДКА -- эквивалентные формализмы, т.е., для каждого НКА
существует эквивалентный ему ДКА, обратное верно по определению.
\item В общем случае ДКА может быть экспоненциально больше (по
количеству состояний) по сравнению с эквивалентным ему НКА.
\item Для любого ДКА существует только один (с точностью до изоморфизма) минимальный ДКА,
эквивалентный ему.
\item Регулярные языки и конечные автоматы -- эквивалентные
формализмы, то есть, для любого КА существует эквивалентный ему
регулярный язык и наоборот.
\item Конечные автоматы замкнуты относительно операций объединения, вычитания, пересечения, дополнения
и звезды Клини.
\end{itemize}
\textbf{Алгоритм} построения ДКА из НКА представлен ниже.
\begin{algorithm}
\DontPrintSemicolon
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{NFA = $$}
\Output{DFA = $$}
\SetAlgoLined
% \SetAlgoNoEnd
$\delta^\prime := \emptyset, q^\prime := \{s | s \in Q\}, S^\prime := \{q^\prime\}$\;
$seen := \{q^\prime\}, queue := [q^\prime]$\;
\While{$queue \neq \emptyset$}{
$src\_states \leftarrow queue$\;
\For{$i \in I$}{
$trg\_states := \{s^{trg} | (s^{src},i,s^{trg}) \in \delta, s^{src} \in src\_states\}$\;
\If{$trg\_states \neq \emptyset$}{
$\delta^\prime \leftarrow (src\_states, i, trg\_states)$\;
$S^\prime \leftarrow trg\_states$\;
\If{$trg\_states \notin seen$}{
$queue \leftarrow trg\_states$\;
$seen \leftarrow trg\_states$\;
}
}
}
}
$F^\prime := \{state\_set \in S^\prime | \exists s \in state\_set, s \in F\}$
\caption{nfa2dfa algorithm AKA ``Subset construction''}
\end{algorithm}
Введем два дополнительных оператора:
\begin{itemize}
\item R -- оператор инвертирования. $L(R(KA)) = \{inverse(w) | w \in L(KA)\}$
\item D -- оператор построения ДКА по НКА.
\end{itemize}
\break
\textbf{Алгоритм} Бжозовского построения минимального ДКА по НКА:\\
$MinDFA = (D \circ R \circ D \circ R) KA$
\break
\textbf{Замечание:} В отличие от большинства других алгоритмов построения минимального ДКА, алгоритм
Бжозовского строит минимальный ДКА по НКА!
Алгоритм проверки, входит ли строка в язык ДКА.
\begin{algorithm}
\DontPrintSemicolon
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{DFA = $, Text=[t_1, t_2 \dots t_n], t_i \in I$}
\Output{$true$ \textbf{or} $false$}
\SetAlgoLined
% \SetAlgoNoEnd
$state := q$\;
\For{$i$ from $1$ to $n$}{
\uIf{$\delta$ is defined on $(state, t_i)$}{
$state := \delta(state, t_i)$\;
}\Else{
\textbf{return} false\;
}
}
\textbf{return} $(state \in F)$\;
\caption{Сопоставление строки с ДКА. Сложность алгоритма: $O(n)$}
\end{algorithm}
Алгоритм проверки, входит ли строка в язык НКА.
\begin{algorithm}
\DontPrintSemicolon
\SetAlgoLined
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{NFA = $, Text=[t_1, t_2 \dots t_n], t_i \in I$}
\Output{$true$ \textbf{or} $false$}
$states := Q$\;
\For{$i$ from $1$ to $n$ \textbf{and} $states \neq \emptyset$}{
$states := \{trg | (src, t_i, trg) \in \delta, src \in states\}$\;
}
\textbf{return} $(\exists s \in states, s \in F)$\;
\caption{Сопоставление строки с НКА. Сложность алгоритма: $O(n * |S|)$}
\end{algorithm}
\textbf{Определение:}
Автомат Мура -- это шестерка $$, где
\begin{itemize}
\item $I$ -- входной алфавит, конечное непустое множество входных символов;
\item $O$ -- выходной алфавит, конечное непустое множество выходных символов;
\item $S$ -- конечное непустое множество состояний;
\item $q$ -- стартовое состояние, $q \in S$;
\item $\delta$ -- функция переходов $\delta: S \times I \rightarrow S$;
\item $\lambda$ -- функция выходов $\lambda: S \rightarrow O$.
\end{itemize}
\textbf{Определение:}
Автомат Мили -- это шестерка $$.
\begin{itemize}
\item $I$ -- входной алфавит, конечное непустое множество входных символов;
\item $O$ -- выходной алфавит, конечное непустое множество выходных символов;
\item $S$ -- конечное непустое множество состояний;
\item $q$ -- стартовое состояние, $q \in S$;
\item $\delta$ -- функция переходов $\delta: S \times I \rightarrow S$
\item $\lambda$ -- функция выходов $\lambda: S \times I \rightarrow O$
\end{itemize}
\textbf{Note:} На практике мы часто работаем с \textit{частично определенными} ДКА, НКА,
автоматами Мура и Мили, т.е., автоматами с частично определенной функцией переходов.
\textbf{Теорема:} Автоматы Мура и Мили -- эквивалентные формализмы.
\textbf{Определение:}
Взвешенный конечный автомат -- это шестерка $$.
\begin{itemize}
\item $I$ -- конечное непустое множество символов (алфавит);
\item $S$ -- конечное непустое множество состояний;
\item $Q$ -- множество стартовых состояний, $Q \subseteq S$;
\item $F$ -- множество конечных состояний, $F \subseteq S$;
\item $\delta$ -- отношение переходов $\delta \subseteq S \times I \times S$
\item $\omega: \delta \rightarrow \mathbb{R}$ -- вес перехода.
\end{itemize}
$\omega$ может быть функцией расстояния, вероятностей, штрафов и т.д., даже не обязательно $\mathbb{R}$.
\textbf{Определение:} Конечно-автоматный преобразователь -- это шестерка
$$.
\begin{itemize}
\item $I$ -- входной алфавит, конечное непустое множество входных символов;
\item $O$ -- выходной алфавит, конечное непустое множество выходных символов;
\item $S$ -- конечное непустое множество состояний;
\item $Q$ -- множество стартовых состояний, $Q \subseteq S$;
\item $F$ -- множество конечных состояний, $F \subseteq S$;
\item $\delta$ -- отношение переходов $\delta \subseteq S \times (I \cup \{\epsilon\}) \times (O \cup \{\epsilon\})\times S$, где $\epsilon$ -- это пустая строка.
\end{itemize}
\textbf{Замечание:} Взвешенный конечно-автоматный преобразователь
определяется аналогично взвешенному конечному автомату.
\break
\textbf{Область применения взвешенных конечно-автоматных
преобразователей:} распознавание речи, синтез речи, распознавание
символов, машинный перевод, различные задачи обработки естественного
языка, включая синтаксический анализ и моделирование языка,
распознавание образов и вычислительная биология.
Задачи, решаемые с помощью конечных автоматов:
\begin{itemize}
\item Исправление ошибок OCR-распознавания CUSIP
\mbox{(https://en.wikipedia.org/wiki/CUSIP)}. Идея алгоритма
заключается в построении взвешенного конечно-автоматного
преобразователя. В нем состояния соответствуют значению контрольной
суммы (по модулю 10), рассчитанной для определенного символа (8
групп по 10 состояний в каждой), а переходы между группами состояний
соответствуют символам CUSIP. Переходы из состояний
8-й группы в конечное состояние соответствует символу контрольной
суммы. Входным алфавитом является множество наблюдаемых
(распознанных) символов. Выходным алфавитом является множество
символов, допустимых в CUSIP. При этом выходной вес на переходе
соответствует правильному (исправленному) символу CUSIP. Вес же
перехода -- это условная вероятность правильного символа при
определенном наблюдаемом. Таким образом, путь с максимальным
произведением заданных на переходах условных вероятностей и дает нам способ
исправления неправильно распознанных символов CUSIP. При этом
правильность контрольной суммы CUSIP обеспечивается структурой
конечно-автоматного преобразователя.
\item Исправление ошибок OCR-распознавания IBAN. Подход, который можно
использовать для этой задачи, ровно тот же, что и в задаче
корректирования CUSIP. Разница заключается длишь в том, что КА
строится для другой контрольной суммы (mod 97) и с использованием
регулярных выражений, задающих форму IBAN для различных стран
европы. Такой КА получится достаточно большим.
\item Наиболее простым способом применения КА является проектирование
ПО, в частности проектирование классов при использовании
объектно-оринетированной парадигмы. Жизненный цикл объекта некоего
класса представляется в виде КА, задающего его поведение, при этом
стартовое состояние КА представляет собой состояние объекта в момент
после его создания конструктором по умолчанию. А переходы
соответствуют вызовам определенных фукнций в моменты, когда объект
находится в определенных состояниях. Этот подход дает возможность
тестировать поведение объекта (и, в общем случае, ПО) в процессе его
жизни. Такого рода тестирование заключается в покрытии таблицы
переходов КА.
\item Задача извлечения именованных сущностей из текста также может быть решена с использованием
взвешенных конечных автоматов. Идея такого алгоритма заключается в том, что классификация
производится пословно на классах B, I, O, E, S (при использовании BIOES нотации), а затем
производится выбор из всех возможных цепочек только тех, которые согласуются с BIOES нотацией,
которую можно задать
с помощью КА. При этом переходы КА взвешены вероятностями, полученными классификационным алгоритмом,
а значит появляется возможность выбрать наиболее вероятную последовательность меток B, I, E, S и O.
Этот подход является в сущности алгоритмом выбора цепочки меток, которая соответствует максимальной
совместной вероятности набора меток, при этом множество цепочек, из которых производится отбор
полностью соответствует BIOES нотации.
\item Автоматы Мура можно использовать, например, для задачи
сопоставление текста с образцами с сохранением информации о том,
какой именно набор образцов ``сработал'' на заданном тексте. Для
решения данной задачи при использовании ДКА необходимо
воспользоваться информацией о том, из каких состояний исходного НКА
``сформировано'' состояние ДКА. Эта информация используется для
формирования символа выходного алфавита, соответствующего
``конечному'' состоянию, которое соответствует любому набору
исходных регулярных выражений. Потенциально выходной алфавит может
содержать $2^n$ элементов, где $n$ -- количество исходных регулярных
выражений.
\item
\end{itemize}
\end{document}