finite-automata - 什么是有限状态自动机，程序员为什么要了解它们？

Question

嗯 - 问题说的是什么。这是我一直听说的事情，但我还没有时间去研究它。

(更新)我可以查找定义……但为什么不(正如@erikson 指出的那样)深入了解您的真实经历和轶事。 Community Wiki'd incase 可以帮助人们投票选出最有见地的答案。到目前为止阅读很有趣，谢谢!

Answer 1

简而言之，这是一种可以用来表达具有具体状态(与量子状态/概率分布相反)的系统的技术。

引用 Wikipedia article :

A finite state machine (FSM) or finite state automaton (plural: automata) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an abstract model of a machine with a primitive internal memory.

那么，这对你意味着什么？简而言之，它是表示您关心的系统从起始状态到结束状态的路径的有效方法。使用正则表达式作为一个相当容易理解的例子，让我们看看模式 AB+C(想象那个加号是一个上标)。我希望这种模式接受诸如“ABC”、“ABBC”、“ABBBC”等字符串。开头是 A，结尾是 C，中间有一些 B(大于或等于 1) .

如果您考虑一下，从图片的角度考虑这个问题几乎更容易。用文本伪造它(我的括号是一个环回弧)，你可以看到 A(左边)是起始状态，C(右边)是右边的结束状态。

      _
     ( ) 
A --> B --> C

从 FSA 开始，您可以前往 Turing Machines 之地，继续您的计算复杂性之旅。 .

但是，您也可以使用状态机来表示真实的行为和系统。在我的世界中，我们使用它们来模拟实际人员使用组件的某些工作流程，这些组件非常不能容忍状态顺序中的错误。就像“A 最好在 C 之前发生，否则会出现非常严重的问题。现在就不可能做到这一点。”