非決定性有限オートマトン
NFA を実装する方法はいくつか存在する。
決定性有限オートマトンに変換する。全ての NFA は DFA に変換可能である。
複数の状態への遷移について、配列のようなデータ構造を使って、遷移可能な状態に印を付ける(状態番号をインデックスとする配列)。印が付いている複数の状態が取りうる状態と見なされ、入力にしたがって取りうる全ての状態について遷移先を判断する(ある状態は入力文字を受け付けない場合もあり、その場合その状態は捨てられる)。このようにして最終的に受容状態に印がついていたら、その入力文字列が受容されたと判断できる。
オブジェクト指向的な実装方法として、NFA をオブジェクトとして、遷移先が複数存在する場合に遷移先の個数ぶんのオブジェクトのコピーを作成してそれぞれに同じ入力文字列(の未入力分)を与えるという方法がある。最終的に受容状態となった NFA オブジェクトが存在したら、その文字列が受容されたと判断できる。現在状態と未入力の入力文字列を引数とした再帰関数の形でも同じことが可能である。