今日は非決定性（有限）オートマトンについて。NFAと略される。このオートマトンは遷移関数が集合を返す。つまり、遷移先がひとつではなく、複数でもなくてもよいというものである。行き先がなくなると、その遷移は終了する。行き先が複数ならば、任意の一つのパスが受理状態で入力が終わるとそのオートマトン自体が受理されたことになる。
また、この非決定性オートマトンは決定性オートマトンに変換することが可能である。なぜならば非決定性オートマトンで実現する可能性のある状態遷移の組をそれぞれ、決定性オートマトンの組にすればよいからである。ただ、この組は各状態集合のべき集合の数になる可能性があるので、指数関数的に増加する可能性がある。
ってこうかくと、いったい何がおもしろいの？といわれるかもしれないけど、おもしろい。なぜかわからんが。何に役に立つかもいまひとつわからないのに。
