(T/F)给定具有空/ε转换的NFA，可以创建另一个接受相同语言但没有空转换的NFA

Question

真或假，并说出原因：

给定具有空/ε转换的 NFA，可以创建另一个接受相同语言但没有空转换的 NFA。

Answer 1

这是真的。这个想法是，对于每个状态，您都可以通过仅遍历 null/epsilon 转换来找到可从中访问的状态集。然后，更新在该状态下终止的所有转换，以在一组可访问状态中终止。此时，可以安全地删除空/厄普西隆转换。

根据您可以依赖的内容，您可以简单地争辩说，具有 null/epsilon 转换的 NFA 描述了一种常规语言，而常规语言具有 DFA，而 DFA 是没有 null/epsilon 转换的 NFA。