Slovník pojmů (ve vývoji)

 \item Ze vstupního DFA $A$ eliminujeme stavy nedosažitelné z počátečního stavu.
\item Najdeme rozklad zbylých stavů na třídy ekvivalence.
\item Konstruujeme DFA $B$ na třídách ekvivalence jakožto stavech. Přechodovou funkci $B$ označíme $\gamma$, mějme $S\in Q_B$. Pro libovolné $q\in S$, označíme $T$ třídu ekvivalence $\delta(q,a)$ a definujeme $\gamma(S,a)=T$. Tato třída musí být stejná pro všechna $a \in S$.
\item Počáteční stav $B$ je třída obsahující počáteční stav $A$.
\item Množina přijímajících stavů $B$ jsou bloky odpovídající přijímajícím stavům $A$.

\pojem{Podmnožinová konstrukce} začíná s NFA $N=(Q_N,\Sigma,\delta_N,q_0,F_N)$. Cílem je popis deterministického DFA $D=(Q_D,\Sigma,\delta_D,\{q_0\},F_D)$, pro který $L(N)=L(D)$.
\begin{itemize}
\item $Q_D$ je množina podmnožin $Q_N$, $Q_D={\cal P}(Q_N)$ (potenční množina). {\footnotesize Nedosažitelné stavy můžeme vynechat.}
\item $F_D=\{S: S\in {\cal P}(Q_N)\ \&\ S \cup F_N \neq \emptyset\}$, tedy $S$ obsahuje alespoň jeden přijímající stav $N$.
\item Pro každé $S\subseteq Q_N$ a každý vstupní symbol $a\in \Sigma$,
$\delta_D(S,a)=\bigcup_{p \in S}\delta_N(p,a)\hbox{.}$
\end{itemize}