非決定性有限オートマトン

NFAは形式的には5タプルで表され、 ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$から構成される

• 有限個の状態${\displaystyle Q}$、
• アルファベットと呼ばれる有限個の入力記号の集合${\displaystyle \Sigma }$、
• 遷移関数${\displaystyle \delta }$ :${\displaystyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$、
• 初期状態（または開始状態）${\displaystyle q_{0}\in Q}$、 そして
• 受理状態（または最終状態）の集合${\displaystyle F\subseteq Q}$。

ここ、${\displaystyle {\mathcal {P}}(Q)}$の冪集合を表す${\displaystyle Q}$。

NFAが与えられた場合${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$、その認識言語は、${\displaystyle L(M)}$は、アルファベット上のすべての文字列の集合として定義されます。${\displaystyle \Sigma }$受け入れられるもの${\displaystyle M}$。

上記の非公式な説明に大まかに対応する形で、文字列にはいくつかの同等の形式的な定義が存在する。${\displaystyle w=a_{1}a_{2}...a_{n}}$受け入れられる${\displaystyle M}$:

• ${\displaystyle w}$状態のシーケンスが受け入れられる場合、${\displaystyle r_{0},r_{1},...,r_{n}}$存在する${\displaystyle Q}$すなわち、
  1. $\displaystyle r_{0}=q_{0}}$
  2. $\displaystyle r_{i+1}\in \delta (r_{i},a_{i+1})}$、 のために${\displaystyle i=0,\ldots ,n-1}$
  3. ${\displaystyle r_{n}\in F}$。

言葉で言うと、最初の条件は、機械が起動状態から始まることを意味します。$q0$2番目の条件は、文字列の各文字が与えられた場合、${\displaystyle w}$機械は遷移関数に従って状態から状態へと遷移します。${\displaystyle \delta }$最後の条件は、機械が受け入れることを示しています。${\displaystyle w}$最後の入力が${\displaystyle w}$機械が受け入れ状態のいずれかで停止する原因となります。${\displaystyle w}$受け入れられる${\displaystyle M}$すべての状態シーケンスが受理状態で終わる必要はなく、いずれか1つが受理状態になれば十分である。そうでなければ、つまり、からに到達することがまったく不可能な場合は、$q0$州へ${\displaystyle F}$以下に${\displaystyle w}$オートマトンが文字列を拒否すると言われている。文字列の集合${\displaystyle M}$は、​​${\displaystyle M}$そしてこの言語は次のように表される${\displaystyle L(M)}$[ ^{5 ] : 320 [ 8 ]​}

• あるいは、${\displaystyle w}$受け入れられる場合${\displaystyle \delta ^{*}(q_{0},w)\cap F\not =\emptyset }$、 どこ${\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}$は再帰的に次のように定義される。
  1. ${\displaystyle \delta ^{*}(r,\varepsilon )=\{r\}}$どこ${\displaystyle \varepsilon }$は空文字列であり、
  2. ${\displaystyle \delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)}$すべての人々のために${\displaystyle x\in \Sigma ^{*},a\in \Sigma }$。

言葉で言うと、${\displaystyle \delta ^{*}(r,x)}$は、ある状態から到達可能なすべての状態の集合です。${\displaystyle r}$文字列を消費することによって${\displaystyle x}$. 文字列${\displaystyle w}$受け入れ状態が${\displaystyle F}$開始状態から到達可能$q0$消費することによって${\displaystyle w}$[ ^{9 ] [ 10 ]​}

上記のオートマトン定義では単一の初期状態を使用していますが、これは必ずしも必要ではありません。NFAは複数の初期状態を持つ場合もあります。複数の初期状態を持つNFAを単一の初期状態を持つNFAに変換する簡単な方法があり、便利な表記法を提供します。

同型写像${\displaystyle \varphi }$自動人形から${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$自動人形へ${\displaystyle (Q',\Sigma ,\delta ',q'_{0},F')}$全単射写像${\displaystyle \varphi :Q\to Q'}$そのため

• $\displaystyle \varphi (q_{0})=q'_{0}}$、
• ${\displaystyle q\in F}$もし、そしてその場合に限り、${\displaystyle \varphi (q)\in F'}$それぞれについて${\displaystyle q\in Q}$、 そして
• ${\displaystyle r\in \delta (q,a)}$もし、そしてその場合に限り、${\displaystyle \varphi (r)\in \delta '(\varphi (q),a)}$それぞれについて${\displaystyle q,r\in Q}$そして${\displaystyle a\in \Sigma }$。

直感的に言えば、2つのオートマトンが同じアルファベットを共有し、一方のオートマトンの状態を体系的に名前変更することで他方のオートマトンが得られる場合、それらは同型であると言える。

NFA -εは形式的には5タプルで表され、${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$から構成される

• 有限個の状態${\displaystyle Q}$
• アルファベットと呼ばれる有限個の入力記号の集合${\displaystyle \Sigma }$
• 遷移関数${\displaystyle \delta :Q\times (\Sigma \cup \{\varepsilon \})\rightarrow {\mathcal {P}}(Q)}$
• 初期状態（または開始状態）${\displaystyle q_{0}\in Q}$
• 一連の州${\displaystyle F}$受容状態（または最終状態）として区別される${\displaystyle F\subseteq Q}$。

ここ、${\displaystyle {\mathcal {P}}(Q)}$の冪集合を表す${\displaystyle Q}$そして${\displaystyle \varepsilon }$空文字列を表します。

州にとって${\displaystyle q\in Q}$、 させて${\displaystyle E(q)}$から到達可能な状態の集合を表す${\displaystyle q}$遷移関数におけるε遷移を追跡することによって${\displaystyle \delta }$つまり、 ${\displaystyle p\in E(q)}$状態のシーケンスがある場合${\displaystyle q_{1},...,q_{k}}$そのため

• ${\displaystyle q_{1}=q}$、
• ${\displaystyle q_{i+1}\in \delta (q_{i},\varepsilon )}$各${\displaystyle 1\leq i<k}$、 そして
• ${\displaystyle q_{k}=p}$。

${\displaystyle E(q)}$これはイプシロン閉包（ε閉包とも呼ばれる）として知られている。${\displaystyle q}$。

集合のε閉包${\displaystyle P}$NFAの状態の集合は、NFAの任意の状態から到達可能な状態の集合として定義されます。${\displaystyle P}$ε遷移に続く。形式的には、${\displaystyle P\subseteq Q}$、 定義する${\displaystyle E(P)=\bigcup \limits _{q\in P}E(q)}$。

ε移動のないNFAと同様に、遷移関数は${\displaystyle \delta }$NFA-ε の は文字列に拡張できます。非公式には、${\displaystyle \delta ^{*}(q,w)}$は、オートマトンが状態から開始したときに到達しうるすべての状態の集合を表します。${\displaystyle q\in Q}$そして文字列を読み取る${\displaystyle w\in \Sigma ^{*}.}$ 機能${\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}$は以下のように再帰的に定義できる。

• ${\displaystyle \delta ^{*}(q,\varepsilon )=E(q)}$各州について${\displaystyle q\in Q,}$そしてどこで${\displaystyle E}$ε閉包を表す。

非公式には：空文字列を読み込むと、オートマトンが状態から遷移する可能性がある${\displaystyle q}$ε閉包の任意の状態へ${\displaystyle q.}$

• ${\textstyle \delta ^{*}(q,wa)=\bigcup _{r\in \delta ^{*}(q,w)}E(\delta (r,a)),}$各州について${\displaystyle q\in Q,}$各文字列${\displaystyle w\in \Sigma ^{*}}$そして各シンボル${\displaystyle a\in \Sigma .}$

非公式に:文字列を読む${\displaystyle w}$オートマトンを状態から駆動する可能性がある${\displaystyle q}$どの州にも${\displaystyle r}$再帰的に計算されたセットにおいて${\displaystyle \delta ^{*}(q,w)}$その後、記号を読みます${\displaystyle a}$それを駆動するかもしれない${\displaystyle r}$ε閉包内の任意の状態へ${\displaystyle \delta (r,a).}$

オートマトンは文字列を受け入れると言われている${\displaystyle w}$もし

${\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \emptyset ,}$

つまり、読んでいる場合${\displaystyle w}$オートマトンを初期状態から駆動する可能性がある${\displaystyle q_{0}}$受け入れ態勢のある州へ${\displaystyle F.}$^{[ 11 ]}

させて${\displaystyle M}$入力に偶数個の0が含まれているか、偶数個の1が含まれているかを判定する、バイナリアルファベットを持つNFA-εとする。なお、0の出現も偶数個の出現とみなす。

正式な表記では、$${\displaystyle M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\delta ,S_{0},\{S_{1},S_{3}\})}$$ここで遷移関係${\displaystyle \delta }$この状態遷移表によって定義できます。

${\displaystyle M}$これは、2 つのDFAの和集合と見なすことができる。1 つは状態を持つ DFA である。${\displaystyle \{S_{1},S_{2}\}}$そしてもう一方の州は${\displaystyle \{S_{3},S_{4}\}}$言語${\displaystyle M}$この正規表現で与えられる正規言語で記述できます${\displaystyle (1^{*}01^{*}01^{*})^{*}\cup (0^{*}10^{*}10^{*})^{*}}$定義します${\displaystyle M}$ε-移動を使用するが${\displaystyle M}$ε移動を用いずに定義することができる。

NFA-εがNFAと等価であることを示すには、まずNFAがNFA-εの特殊なケースであることに注意し、すべてのNFA-εに対して等価なNFAが存在することを示せばよい。

ε個の移動を持つNFAが与えられた場合${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F),}$ NFAを定義する${\displaystyle M'=(Q,\Sigma ,\delta ',q_{0},F'),}$どこ

${\displaystyle F'={\begin{cases}F\cup \{q_{0}\}&{\text{ if }}E(q_{0})\cap F\neq \{\}\\F&{\text{ otherwise }}\\\end{cases}}}$

そして

${\displaystyle \delta '(q,a)=\delta ^{*}(q,a)}$各州について${\displaystyle q\in Q}$そして各シンボル${\displaystyle a\in \Sigma ,}$拡張遷移関数を使用する${\displaystyle \delta ^{*}}$上記で定義されています。

遷移関数を区別する必要がある${\displaystyle M}$そして${\displaystyle M',}$すなわち${\displaystyle \delta }$そして${\displaystyle \delta ',}$弦への拡張、${\displaystyle \delta ^{*}}$そして${\displaystyle \delta '^{*},}$それぞれ。構造上、${\displaystyle M'}$ε遷移を持たない。

証明できる${\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}$各文字列について${\displaystyle w\neq \varepsilon }$長さに関する帰納法によって${\displaystyle w.}$

これに基づいて、次のことが示せる。${\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}}$もし、そしてその場合に限り、${\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \{\},}$各文字列について${\displaystyle w\in \Sigma ^{*}:}$

• もし${\displaystyle w=\varepsilon ,}$これは、${\displaystyle F'.}$
• そうでなければ、${\displaystyle w=va}$と${\displaystyle v\in \Sigma ^{*}}$そして${\displaystyle a\in \Sigma .}$

から${\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}$そして${\displaystyle F\subseteq F',}$我々は持っています$${\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};}$$私たちはまだ「${\displaystyle \Rightarrow }$" 方向。

• もし${\displaystyle \delta '^{*}(q_{0},w)}$状態を含む${\displaystyle F'\setminus \{q_{0}\},}$それから${\displaystyle \delta ^{*}(q_{0},w)}$同じ状態を含み、それは${\displaystyle F}$。
• もし${\displaystyle \delta '^{*}(q_{0},w)}$含む${\displaystyle q_{0},}$そして${\displaystyle q_{0}\in F,}$それから ${\displaystyle \delta ^{*}(q_{0},w)}$また、状態も含まれています${\displaystyle F,}$すなわち${\displaystyle q_{0}.}$
• もし${\displaystyle \delta '^{*}(q_{0},w)}$含む${\displaystyle q_{0},}$そして${\displaystyle q_{0}\not \in F,}$しかし${\displaystyle q_{0}\in F',}$すると、${\displaystyle E(q_{0})\cap F}$、そして同じ状態である必要があります${\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a)).}$^{[ 12 ]}

NFAはDFAと等価であるため、NFA-εもDFAと等価である。