regex - 转换 RE -> NFA

Question

我有一个关于将正则表达式转换为非确定性有限状态自动机的问题：

将 (a*|b*)* 转换为 NFA。我的尝试如下：

我完全偏离标准了吗？还是有些地方？

NB E => ε

Answer 1

您的 NFA 与 匹配的语言相同(a*|b*)*，因此答案是正确的。

但是，有许多 NFA 匹配相同的语言，在您的情况下，可以删除至少三个 epsilon 箭头。不过，它不会比您的建议更正确。

(a*|b*)*也可以简化正则表达式，而不改变语义。例如(a|b)*等价于(a*|b*)*。如果你仔细想想，FA 可以这么简单：