部分集合構成法
次に状態 { 1 , 2 , 3 } {\displaystyle \{1,2,3\}} において入力 0 {\displaystyle 0} が与えられた際の遷移について、状態 1 {\displaystyle 1} から状態 2 {\displaystyle 2} への遷移と状態 2 {\displaystyle 2} から状態 4 {\displaystyle 4} への遷移が考えられる。ここで状態 2 {\displaystyle 2} 及び 4 {\displaystyle 4} はいずれもε-遷移を持たないから、 δ ′ ( { 1 , 2 , 3 } , 0 ) = { 2 , 4 } {\displaystyle \delta '(\{1,2,3\},0)=\{2,4\}} であることが分かる。以降このようにして、変換後の遷移規則の検討を新しい状態の集合が発生するたびに行う。すると下に示されるようなDFAが得られる。
今回の例では、変換前のNFAは4状態からなるため状態の冪集合の大きさは16であるが、実際に到達可能な状態の集合はたったの5つである。
まず単純な場合として、文字を読み取らずとも遷移すること(いわゆるε-遷移)を許さないNFAを考える。このようなNFAを5つ組 ( Q , Σ , δ , q 0 , A ) {\displaystyle (Q,\Sigma ,\delta ,q_{0},A)} を以って定める。このNFAを部分集合構成法を用いて変換するとDFA ( P ( Q ) , Σ , δ ′ , { q 0 } , F ′ ) {\displaystyle ({\mathcal {P}}(Q),\Sigma ,\delta ',\{q_{0}\},F')} が得られる。ただし、
δ ′ ( R , a ) = ⋃ r ∈ R δ ( r , a ) {\displaystyle \delta '(R,a)=\bigcup _{r\in R}\delta (r,a)}
F ′ = { R ∈ P ( Q ) | R ∩ F ≠ ∅ } {\displaystyle F'=\{R\in {\mathcal {P}}(Q)|R\cap F\neq \emptyset \}}
である。
上述の方法は最も単純な方法であるが、初期状態から到達できない状態が大量に生成される可能性がある。これを避けるためには、初期状態から任意の文字列を与えて遷移を行うことを繰り返し、実際に到達できた状態集合だけを変換後の状態とする必要がある。