0

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

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

在此处输入图像描述

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

NB E => ε

4

1 回答 1

3

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

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

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

有限自动机等价于 (a|b)*

于 2011-05-09T17:37:33.380 回答