finite-automata - 如何构造有限自动机

Question

我必须创建一个确定性有限自动机，接受偶数为 1 并以 0 结尾的字符串集。我应该将 0 作为该集合中的字符串包含在内吗？我该怎么做？

Answer 1

我应该0作为这个集合中的字符串包含吗？

是的

我该怎么做？

要构造有限自动机，您需要识别状态和转移。如果您能够识别“不可区分”字符串的等价类，Myhill-Nerode 定理允许您找到有限自动机的必要（和充分！）状态。

从这个意义上说，两个字符串xandy是无法区分的，如果对于任何其他 string z，要么两者xz和yz都在该语言中，要么两者都不是。

在您的情况下，让我们尝试识别等价类。空字符串在某个等价类中。该字符串0位于不同的等效类中，因为您可以将空字符串添加到0该语言中并获取一个字符串（而您不能将空字符串添加到空字符串中以获取该语言的字符串）。到目前为止，我们已经找到了两个不同的等价类——一个用于空字符串，一个用于0. 在我们的 FA 中，这两者都需要不同的状态。

字符串1呢？0它与空字符串有区别，因为您可以添加10到1get 110，该语言中的字符串，但您不能将其添加到0或空字符串中以获取该语言中的字符串。所以我们还有另一个状态。

字符串00呢？该字符串不在该语言中，并且不能将其他字符串添加到该字符串中以获得该语言的字符串。这是另一个等价类。事实证明，接下来的字符串01和10也在这个类中。

该字符串11最终与空字符串属于同一类：您可以将语言中的任何字符串添加到该语言中11并获取该语言中的另一个字符串。如果您尝试所有长度为 3 的字符串，您会发现所有这些都已属于上述类别之一，您可以在此时停止检查。

所以我们有四种状态——我们称它们[-]为 、[0]、[1]和[00]。现在我们找出过渡。

如果你进入0，[-]你需要去[0]……如果你进入1，你需要去[1]。其余的，只需弄清楚通过添加到规范字符串会得到什么字符串，以及生成的字符串将属于哪个类......然后进入那个状态。