面向对象的程序能被看作是有限状态机吗？

Question

这可能是一个哲学/基本问题，但我只想澄清这一点。

在我看来，有限状态机是一种建模系统的方法，在这种方法中，系统的输出不仅取决于当前的输入，而且取决于系统的当前状态。此外，顾名思义，有限状态机可以在有限的N个状态中分割，并具有其各自的状态和行为。

如果这是正确的，那么每一个具有数据和函数成员的对象都不应该是我们面向对象模型中的状态，使任何面向对象的设计都成为一个有限的状态机吗？

如果这不是对象设计中对FSM的解释，那么人们在软件中实现FSM究竟意味着什么呢？我是不是遗漏了什么？

谢谢

Answer 1

问题不在于某物是“是”还是“不是”有限状态机。一个有限状态机是一个心理模型，如果它可以被认为是一个整体的话，它可能对理解某件事情很有用。

通常，有限状态机模型适用于具有少量状态的事物，如规则语法或计算机的指令排序器。

Answer 2

直接回答你的问题:几乎肯定不是。对于面向对象编程，似乎没有正式的数学理论，就像lambda微积分和/或组合逻辑下的函数式编程，或者图灵机不像普通的旧命令式编程那样。

有关更多信息，请参见这个堆叠溢出问题。

我的猜测是，没有一个基本的数学理论是为什么每个人都知道什么是“物体”时，他们看到一个，但没有人看到“物体”与其他人完全相同。

Answer 3

不，反正也不是。有限状态机通常只记住一条数据:它的当前状态。

FSM的一个典型应用程序是词法或解析。例如，当我们进行lexing时，(通常)很容易根据当前状态和输入的值对每个可能的输入进行编码。

例如，我们可能有一个数字状态，在这个状态中，我们正在读取一个数字的数字。如果我们读取的下一个字符是数字，则保持数字状态。如果是空格或制表符，我们将返回数字，然后进入某个WHITE_SPACE状态，或按该顺序进行。

现在，在一个典型的FSM (特别是在软件中实现的FSM )中，我们最终得到的是一些技术上不太适合FSM本身的FSM。例如，当我们读取一个数字的数字时，您通常会保存第一个数字的位置，所以当您到达末尾时，您可以很容易地计算出这个数字的值。

FSM本身有一些限制--它没有计数机制。例如，考虑使用"/“开始注释和使用"/”结束注释的语言。它的lexer可能会有一个注释状态，当它看到一个“/”标记时，它就会输入这个状态。目前它无法检测另一个"/“状态(除非添加另一个像COMMENT2这样的状态)，并意识到它正在处理一个嵌套的注释。相反，在注释状态中，它会将*/识别为告诉它离开注释状态，而其他任何东西都会使它处于注释状态。

如前所述，您当然可以为嵌套的注释包括一个COMMENT2状态--在这种情况下，还可以包含一个COMMENT3状态，等等。然而，在某个时候，您将厌倦添加更多的状态，这将决定您允许注释的最大嵌套深度。使用其他形式的解析器(即，不是纯状态机，而是有一些内存可以让它计数的东西)，您可以直接跟踪嵌套深度，因此您可以保持在注释状态，直到达到一个平衡第一个状态的密切注释令牌，所以计数器返回到0，然后离开注释状态。

然而，正如我所说，当你添加这样的计数器时，你所拥有的不再是真正的FSM。同时，它实际上非常接近--具体来说，足够接近，你可以通过添加更多的状态来模拟计数器。

然而，在典型的情况下，当有人谈到在软件中实现FSM时，他们会合理地保持它的“纯”。特别是，软件将只根据当前状态和输入本身的值对当前输入作出反应。如果反应取决于任何其他因素，他们通常不会称其为状态机(至少如果他们知道自己在说什么)。