Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我有一个关于将正则表达式转换为非确定性有限状态自动机的问题:
将 (a*|b*)* 转换为 NFA。我的尝试如下:
我完全偏离标准了吗?还是有些地方?
NB E => ε
您的 NFA 与 匹配的语言相同(a*|b*)*,因此答案是正确的。
(a*|b*)*
但是,有许多 NFA 匹配相同的语言,在您的情况下,可以删除至少三个 epsilon 箭头。不过,它不会比您的建议更正确。
(a*|b*)*也可以简化正则表达式,而不改变语义。例如(a|b)*等价于(a*|b*)*。如果你仔细想想,FA 可以这么简单:
(a|b)*