ε-動作付きNFAからε-動作を除去
定義1. ε-動作付きNFA
定理1. ε-動作の除去
\begin{align} &\forall L\in\Sigma^*\\ &(Lを受理する\epsilon\mathrm{-}動作付き\mathrm{NFA}が存在する \Longleftrightarrow Lを受理する\mathrm{NFA}が存在する) \end{align}
ε-動作付きNFAには、ε-動作を含まない等価なNFAが存在します!
当サイトでは述語論理の記述を多用します。 一般の書籍・論文ではあまり見られない記号を使用する場合もありますので、 本サイトで使用する数学記号 を参照しながらご覧ください。
\begin{align} &\forall L\in\Sigma^*\\ &(Lを受理する\epsilon\mathrm{-}動作付き\mathrm{NFA}が存在する \Longleftrightarrow Lを受理する\mathrm{NFA}が存在する) \end{align}