部分集合構成法

順序機械、有限オートマトン、死状態と推移不許可、有限オートマトンの決定性と非決定性

　非決定性有限オートマトンというのは、1つの記号入力に対して複数の状態推移の可能性を持つ機械だったよ。ということはある入力記号列に対して、到達可能となるのは、1つの状態ではなくて状態の集合だということになるよ。この到達可能な状態集合の中に、1つでも最終状態（つまり受理（1）を出力する状態）が含まれていれば、この記号列は受理されたというのだったよ。
　さて、2つの有限オートマトンがあって、記号列入力に対してつねに同じ出力をする（つまり受理する記号列と受理しない記号列が同じ）なら、この2つは等価だといったよ。ということは、非決定性有限オートマトンと決定性有限オートマトンの間でも、この等価性が成り立つ場合があるよ。
　実際、ある非決定性有限オートマトンについて、各記号列入力によって到達可能な状態集合のそれぞれに、1つの状態を対応させて、最終状態を含む状態集合に対応する状態は最終状態である、と決めると、この非決定性有限オートマトンと等価な決定性有限オートマトンを新しく作ることができるよ。このやり方を部分集合構成法というよ。