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

朝から衝撃を受ける。決定性有限オートマトンの出力が複数の状態を許したようなものが非決定性有限オートマトンという感じだが、非決定性有限オートマトンも正則言語(決定性有限オートマトンによりacceptされる言語、だったはず)であるらしい。そんでもって、そういうのが存在するというだけでなく変形させる具体的なアルゴリズムもあるとのことで朝からびびった。