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

  количеству состояний) по сравнению с эквивалентным ему НКА.
\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]$\;