finite-automata - DFAとループ、NFAと再帰の間には関係がありますか？

Question

DFAはループでシミュレートでき、NFAは再帰的方法でシミュレートできると聞きました。それがどのように機能するのかわかりません。誰か私に例を教えてもらえますか？

Answer 1

ある意味、確かに。do...whileDFAは、現在の状態に基づいてステートメントを含むループを作成することで簡単にシミュレートswitchできますが、NFAのシミュレーターは、ツリーを検索するものと考えることができます（深さ優先探索は再帰的ですが、想像することもできます）。幅優先探索）。これには実際には形式的なものはなく、シミュレーターを実装する方法についてのカジュアルな観察にすぎません。