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]$\;
  \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}
</latex>
----
<latex>
Введем два дополнительных оператора:
\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