将DFA减少为NFA

Question

我正在尝试找出一个问题，在那里我必须为给定的语言绘制一个NFA。

语言是{ w | the final five symbols of w include two a's and three b's }。

我相信我有一个DFA，不确定是否有一个更精简的版本。如果有人能帮我看看，那会很有帮助的。我觉得好像可以把它简化成一个相当小的NFA。

​

​

Answer 1

首先，您所拥有的不是a；状态DFA显然是不确定的：

带a的

• 您可以访问a和b
• 您可以访问a和s

的b

其次，由于在FSA中只能计算状态(没有堆栈)，因此必须跟踪在状态空间的最后5个字符中看到的每个符号的数量。只要想一想你需要多少不同的组合，然后转换就会很明显。这是您可以用来解决此练习的最小NFA。