読者です 読者をやめる 読者になる 読者になる

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

計算理論

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