Applications of Finite State Machines (Алексей Чеусов, LVEE-2019) — различия между версиями

\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}
</latex>
<latex>
Языком КА является множество различных последовательностей символов алфавита, допускаемых
конечным автоматом, т.е., цепочек символов вдоль пути от стартового до конечного состояния КА.

\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}

</latex>
<latex>
\textbf{Теоремы}:
\begin{itemize}
\item НКА и ДКА -- эквивалентные формализмы, т.е., для каждого НКА
  существует эквивалентный ему ДКА, обратное верно по определению.
\item В общем случае ДКА может быть экспоненциально больше (по
  количеству состояний) по сравнению с эквивалентным ему НКА.
\item Для любого ДКА существует только один (с точностью до изоморфизма) минимальный ДКА,
  эквивалентный ему.
\item Регулярные языки и конечные автоматы -- эквивалентные
  формализмы, то есть, для любого КА существует эквивалентный ему
  регулярный язык и наоборот.
\item Конечные автоматы замкнуты относительно операций объединения, вычитания, пересечения, дополнения
  и звезды Клини.
\end{itemize}

</latex>
<latex>
\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]$\;

\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</latex>
<latex>
\textbf{Область применения взвешенных конечно-автоматных
  преобразователей:} распознавание речи, синтез речи, распознавание
символов, машинный перевод, различные задачи обработки естественного
языка, включая синтаксический анализ и моделирование языка,
распознавание образов и вычислительная биология.

Задачи, решаемые с помощью конечных автоматов:
\begin{itemize}
\item Исправление ошибок OCR-распознавания CUSIP
  (\href{https://en.wikipedia.org/wiki/CUSIP}{https://en. wikipedia.org/wiki/CUSIP}). Идея алгоритма