finite-automata - DFA和Loop、NFA和递归之间有关系吗？

Question

听说DFA可以用Loop模拟，NFA可以用递归模拟。我不明白这是怎么回事。谁能给我一个例子？

Answer 1

从某种意义上说，当然。DFA 可以通过基于当前状态编写一个do...while包含语句的循环来轻松模拟switch，而您可以将 NFA 的模拟器视为在树上进行搜索（深度优先搜索是递归的，尽管您可以想象广度优先搜索）。这实际上没有任何形式，只是对如何实现模拟器的随意观察。