dfa - 画出一个 FSA 来识别：(A∗ | AB+)。（条形超出了其他运算符的范围，因此它等于：(A∗) | (AB+)。）使用尽可能少的状态

Question

我已经附上了我所拥有的。我的问题是我不知道它是否正确，以及我是否使用了尽可能少的状态来回答这个问题。非常感谢对我目前做错的任何帮助这是我目前所拥有的

Answer 1

我将首先创建两个 FSA，每个分支一个。

因为A*你只需要一种状态。

因为AB+你需要三种状态。

然后你合并两者。假设它不一定是确定性的，那么整个 FSA 最终也会有三个状态，其中两个是最终状态。

当您标记您的问题时dfa——确定性 FSA 总共需要 4 个状态：

启动状态：1；最终状态：1,2,3,4

过渡：

1 - a -> 2
2 - a -> 4
2 - b -> 3
3 - b -> 3
4 - a -> 4

这是一个识别 (a*|ab+) 的 DFA：