定理. DFAとNFAの言語受理能力の等価性

\begin{align} \forall L\in\Sigma^* (Lを受理するNFAが存在する\Longleftrightarrow Lを受理するDFAが存在する) \end{align}

証明

\begin{align} &「\Leftarrow」は明らか。 以下「\Rightarrow」が成り立つことを証明する。\\ &すなわち、ある言語L\in\Sigma^*を受理する任意の非決定性有限オートマトンA=(Q,\Sigma,\delta,q_0,F)について、\\ &Aと等価な決定性有限オートマトンA'=(Q,\Sigma,\delta',q_0',F)が構成されることを示す。\\ \end{align}