-
Notifications
You must be signed in to change notification settings - Fork 0
/
17_2019_Cheusov.tex
283 lines (257 loc) · 20.3 KB
/
17_2019_Cheusov.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
\documentclass[10pt, a5paper]{article}
\input{preamble.tex}
\switchlang{ru}
\begin{document}
\title{Применение аппарата конечных автоматов}
\author{Чеусов Алексей, Минск, Беларусь \footnote{\url{[email protected]}, \url {https://lvee.org/ru/abstracts/308}}}
\begin{document}
\maketitle
\begin{abstract}
In this presentation we define the finite state automata (FSA), Moore and Mealy machines, and Finite State Transducers. We\-ighted and stochastic finite state machines are described. Also, a few well-known and custom algorithms based on finite state machines, are described.
\end{abstract}
Аппарат конечных автоматов -- один из базовых и наиболее важных
понятий в информатике и программировании. Конечные автоматы изучаются
во всех без исключения университетах и институтах по специальностям,
так или иначе связанным с информатикой и программированием. Тем не
менее, по моему мнению недостаточное внимание в нашей системе
образования уделяется практическому их применению, что, на моей
взгляд, негативно сказывается на уровне подготовке отечественных
программистов. Данным докладом хотелось бы хотя бы частично
ликвидировать это досадную ситцацию, и пробудить интерес к во
многом забытым конечным автоматам. С этой целью будут приведены
примеры практических задач, реашемых с их помощью.
Прежде всего хочется сказать, что данная статья является дополнением
к презентации, доступной на сайте \url{http://lvee.org} \linebreak или по ссылке ~
\href{http://www.mova.org/~cheusov/pub/lvee/2019/fsa\_presentation.pdf}{http://www.mova.org/\textasciitilde\,cheusov/pub/lvee/2019/fsa\_presentation.pdf}.
Начать следует с определений и теорем, хорошо знакомых любому
выпускнику ВУЗ-а по технической специальности.
\textbf{Определение:} Недетерминированным конечным автоматом \linebreak (НКА) называется пятерка
\mbox{$<I,S,Q,F,\delta>$}, где
\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{Определение:} Детерминированным конечным автоматом \linebreak (ДКА) является пятерка $<I,S,q,F,\delta>$, где
\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}[h!]
\DontPrintSemicolon
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{NFA = $<I,S,Q,F,\delta>$}
\Output{DFA = $<I,S^{\prime},q^\prime,F^{\prime},\delta^{\prime}>$}
\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}
\textbf{Алгоритм} Бжозовского построения минимального ДКА по \linebreak НКА:\\
$MinDFA = (D \circ R \circ D \circ R) KA$
\textbf{Замечание:} В отличие от большинства других алгоритмов построения минимального ДКА, алгоритм
Бжозовского строит минимальный ДКА по НКА!
\newpage
Алгоритм проверки, входит ли строка в язык ДКА.
\begin{algorithm}[h!]
\DontPrintSemicolon
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{DFA = $<I,S,q,F,\delta>, 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 = $<I,S,Q,F,\delta>, 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{Определение:}
Автомат Мура -- это шестерка $<I,O,S,q,\delta, \lambda>$, где
\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{Определение:}
Автомат Мили -- это шестерка $<I,O,S,q,\delta, \lambda>$.
\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{Определение:}
Взвешенный конечный автомат -- это шестерка $<I,S,Q,F,\delta, \omega>$.
\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{Определение:} Конечно-автоматный преобразователь -- это шестерка
$<I,O,S,Q,F,\delta>$.
\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{Замечание:} Взвешенный конечно-автоматный преобразователь \linebreak
определяется аналогично взвешенному конечному автомату.
\break
\textbf{Область применения взвешенных конечно-автоматных
преобразователей:} распознавание речи, синтез речи, распознавание
символов, машинный перевод, различные задачи обработки естественного
языка, включая синтаксический анализ и моделирование языка,
распознавание образов и вычислительная биология.
Задачи, решаемые с помощью конечных автоматов:
\begin{itemize}
\item Исправление ошибок OCR-распознавания CUSIP
(\href{https://en.wikipedia.org/wiki/CUSIP}{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$ -- количество исходных регулярных
выражений.
\end{itemize}
\end{document}