非決定性有限オートマトンは、決定性オートマトンにできるらしい。 2008/04/22

よくわかってないけど、とりあえずメモ

（１）非決定性により、有限オートマトンの計算能力は向上しない。
（２）非決定性有限オートマトンの方が設計が容易。
※（１）非決定性オートマトンで実行できることは決定性オートマトンでも実行できる。

非決定性オートマトンで設計して、あとで決定性オートマトンにする。

• 非決定性有限オートマトン - Wikipedia

参考
計算論への入門―オートマトン・言語理論・チューリング機械 (スタンダードテキスト)
エフィーム キンバー カール スミス Efim Kinber