我想为语言构造一个DFA：所有字符串的集合，使得每个五个连续符号的块包含至少两个0。如何记录最近5个条目。总之如何解决这类问题。我在互联网上获得了DFA图但却无法理解。任何人都可以解释一下。
我有一个答案，但我不确定它是否是最有效的。在解决问题的过程中，我将尝试解释我的理解。
我们必须构造一个DFA，使每5个长度的子串包含至少2个0。因此，语言将包含所有字符串<= 5，没有限制+字符串长度（> = 5），具有给定的限制。
问题的难点在于我们必须追踪两件事：
a）弦的长度
b）检查5长度子串是否至少有2个0。
我将尝试绘制所有可能的状态：DFA
我们跟踪它们出现在子字符串中的0和1。
一旦我们在一个5长子字符串[出现在树的第5层]得到2 0，我们将回到初始状态并再次开始。我们扩展树，直到每5个长度的子串到达所需的状态为2 0。然后，我们再次分支到树的开头。我们已经确保我们不会以这种方式违反规则的任何5长度子字符串。
我能够找到它的解决方案，但是，它可能不是最有效的。我的解决方案是一个完整的二叉树，就像一个概率树，即如果0 - 0 - 0 - 0 - 0真实状态0 - 0 - 0 - 0 - 1真实状态0 - 0 - 0 - 1 - 1真实状态0 - 0 - 1 - 1 - 1真实状态0 - 1 - 0 - 0 - 0真实状态1 - 0 - 0 - 0 - 1真实状态......然而，它背后的想法是，每当你完成所有真实状态，你添加了4种不同的状态。因此，在最后一个状态如果是真的，它将返回到第一个原始状态。
如果您希望接受这样的字符串，您可以使用一种好的方法。
- >你不想要11111,11110,11101,11011,10111,01111，
作为子串因为只有这些少于2 0
您绘制一个没有上述字符串作为子字符串的DFA，并获得一个好的简单和短DFA