theory - 你怎么知道有限自动机需要多少个状态？

Question

我附上了一张关于我的问题的图片。因此，对于这个问题，它说要制作一个接受以 aa 或 bb 开头/结尾的字符串的 FA。我的问题是你怎么知道什么时候停止添加状态？就像为什么 5 个州而不是显示的 9 个州就足够了？

标签： theoryfinite-automata

Answer 1

给定语言的正式描述，我们可以通过算法将其转换为有限状态自动机，并且必须有一种算法可以找到最小的自动机（如果没有别的，则通过枚举，因为可能性是有限的）。然而，给定自然语言描述，我们（还）没有算法将其翻译成自动机或其他形式的描述。

但是，在这种情况下，我们可以推理：

• 看到“”、“a”和“b”之后的状态必须是不同的，因为它们的结果会根据下一个字符是“a”还是“b”而有所不同。（“a”后跟“a”被接受，而“b”后跟“a”尚未[尚未]被接受。并且“a”后跟“a”被接受，而“”后跟“a”尚未被接受]， 等等。）
• “aa”和“bb”达到的两个状态是相同的，可以合并，将自动机减少到八个状态。
• 否则，在最初看到“ab”或“ba”之后，我们必须有不同的状态：
  • 最后看到的字符是“aa”。（如果是结束状态，则必须接受此状态，如果收到“a”，则必须通向自身[或同构状态]，如果收到“b”，则必须通向不同的状态。）
  • 最后看到的字符是“bb”。（与上述类似，但交换收到“a”或“b”时发生的情况。）
  • 最后看到的字符是“ab”。（如果收到“b”，则此状态必须导致“bb”-was-last-seen 状态，但如果收到“a”则不会。）
  • 最后看到的字符是“ba”。（类似于上面但交换了。）
• 这四种状态也必须不同于最初的四种状态：
  • 无论收到什么，初始“a”状态和初始“b”状态都必须导致接受，而后面的四个状态都不能这样做。
  • 最初的“”状态不能在多一封信后导致接受，而后面的四个状态都可以在收到适当的信时。
  • 在开始时看到“aa”或“bb”的状态必须只导致接受，而后面的四种状态都不能导致无条件接受。

因此，我们必须有八个状态。