呃 - 问题所说的。这是我一直听说的事情，但我还没来得及调查它。
（更新）我可以查找定义......但为什么不（正如@erikson 指出的那样）深入了解您的真实经历和轶事。Community Wiki'd incase 可以帮助人们投票选出最有见地的答案。到目前为止有趣的阅读，谢谢！
Brabster
问问题
3554 次
12 回答
13
简短的回答，这是一种可以用来表达具有具体状态的系统（与量子状态/概率分布相反）的技术。
引用维基百科的文章：
有限状态机 (FSM) 或有限状态自动机（复数：自动机）或简称为状态机，是由有限数量的状态、这些状态之间的转换和动作组成的行为模型。有限状态机是具有原始内部存储器的机器的抽象模型。
那么，这对你意味着什么？简而言之，它是表示您关心的系统从起始状态到结束状态的路径的有效方法。使用正则表达式作为一个相当容易理解的示例，让我们看一下模式 AB+C（想象那个加号是一个上标）。我希望这种模式能够接受诸如“ABC”、“ABBC”、“ABBBC”等字符串。A 在开头，C 在结尾，中间有一些 B（大于或等于一个） .
如果您考虑一下，从图片的角度考虑这一点几乎更容易。用文本伪造它（我的括号是一个环回弧），您可以看到 A（在左侧）是起始状态，C（在右侧）是右侧的结束状态。
_
( )
A --> B --> C
从 FSA 出发，您可以前往图灵机领域，继续您的计算复杂性之旅。
但是，您也可以使用状态机来表示真实的行为和系统。在我的世界里，我们使用它们来模拟实际人员的某些工作流程，这些工作流程非常不容忍状态顺序错误的组件。如，“A 最好在 C 之前发生，否则会出现非常严重的问题。现在不可能做到这一点。”
于 2008-12-12T21:44:29.047 回答
9
You could look it up, but what the hell. Intuitively, a finite state automaton is an abstraction of something that has some finite number of states, and rules by which you can go from state to state. A state is something for which a true or false statement can be made, and a rule is a way that you change from one state to another. So, you could have, say, two states: "I'm at home" and "I'm at work" and two rules, "go to work" and "go home."
It turns out that you can look at machines like this mathematically, and find there are things they can and cannot do. Regular expressions are basically a way of describing a finite state machine in which the states are a set of different strings, and the rules move you from state to state based on the next character read. You can prove that. But you can also prove that no finite state machine can tell whether or not the parentheses in an expression are matched (via the pumping lemma for FSAs.)
The reason you should learn about FSAs is that they can be used to solve many problems: string matching, control of systems, business process descriptions, digital circuit design. They're also inherently pretty.
Formally, an FSA is a algebraic structure F = ⟨Σ, S, s0, F, δ⟩ where Σ is the input alphabet, S is a set of states, s0 ∈ S is a particular start state, F ⊆ S is a set of accepting states, and δ:S×Σ → S is the state transition function.
于 2008-12-12T21:46:53.020 回答
6
in OOP terms: if you have an object with methods that you call on certain events, and some (other) methods that have different behaviour depending on the previous calls.... surprise! you have a state machine!
now, if you know the theory, you don't have to rethink it all. you simply say: "piece of cake, it's just a state machine" and go on to implement it.
if you don't know the theory you'll think about it for a while, write some clever hacks, and get something that's difficult to explain and document... because you don't have the words to describe it
于 2008-12-12T21:58:01.297 回答
2
Every programmer should know about them because they are an excellent tool for certain kinds of problems, where the usual 'iterative-thinking' approach would yield nasty, complex code.
A typical example is game AI, where NPCs have different states that change according to where the player is, something like:
- NPC_STATE_IDLE
- NPC_STATE_ALERT (player at less than 100 meters)
- NPC_STATE_ENGAGE (player attacked NPC)
- NPC_STATE_FLEE (low on health)
where a FSM can describe easily the transitions and help perform complex reasoning about the system the FSM is describing.
于 2008-12-12T21:44:37.330 回答
2
You need state machines whenever you have to release your thread before you have completed your operation.
Since web services are often not statefull, you don't usually see this in web services--you re-arrange your URL so that each URL corresponds to a single path through the code.
I guess another way to think about it could be that every web server is a FSM where the state information is kept in the URL.
You often see it when processing input. You have to release your thread before the input has all been completed, so you set a flag saying "input in progress" or something like that. When done you set the flag to "awaiting input". That flag is your state monitor.
More often than not, a FSM is implemented as a switch statement that switches on a variable. Each case is a different state. At the end of the case, you may set the state to a new value. You've almost certainly seen this somewhere.
The nice thing about a FSM is that you can make the state a part of your data rather than your code. Imagine that you need to fill out 1000 items in the database. The incoming data will address one of the 1000 items, but you generally don't have enough data to complete the operation.
Without an FSM you might have hundreds of threads waiting around for the rest of the data so they can complete processing and write the results to the DB. With a FSM, you write the state to the DB, then exit your thread. Next time you can check the incoming data, read the state from the thread and that should give you enough info to determine what code to run.
Nearly every FSM operation COULD be done by dedicating a thread to it, but probably not as well (The complexity multiplies based on number of states, whereas with a state machine the rise in complexity is more linear). Also, there are some conceptual design issues--examining your code at the state level is in some cases much easier than examining it at the line of code level.
于 2008-12-12T21:52:37.453 回答
2
Good answers above. I would only add that FSA are primarily a thinking tool, not a programming technique. What makes them useful is they have nice properties, and anything that acts like one has those properties. If you can think of something as an FSA, there are many ways you can build it:
as a regular expression
as a state-transition table
as a while-switch-on-state loop
as a goto-net (horrors!)
as simple structured program code
etc. etc.
If somebody says something is a FSA, you can immediately know what they are talking about, no matter how it is built.
于 2008-12-12T22:01:14.317 回答
2
Important: If you are a "visual" style learner, stop everything you are doing and go to this link ... Right Now.
If you are a "visual" learner, here is an excellent link that gives a very accessible introduction.
It looks like you've already approved an answer, but if you appreciate "visual" introduction to new concepts, as is common, you really should check out the link. It is simply outstanding.
(Note: the link points to a discussion of DFA and NDFA in the context of regular expressions -- with animated interactive diagrams)
于 2009-01-03T18:52:25.773 回答
1
于 2008-12-12T21:28:50.357 回答
1
What it is is better answered on other sites (such as Wikipedia), because there are pretty extensive answers out there already.
Why you should know them: Because you probably implemented them already.
Any time your code has a limited number of possible states (that's the "finite state" part) and switches to another one once some input/event happend (that's the "machine" part) you've written a finite state machine.
It is a very common tool and knowing the theoretical basics for that, being able to reason about it and knowing how to combine two FSMs into a single one that does the same work can be a great help.
于 2008-12-12T21:49:15.480 回答
1
FSAs are great data structures to understand because any chance you have to implement them, you're working at the lowest level of computational complexity on the Chomsky hierarchy. A great example is in word morphology (how parts of words come together). A lot of work has been done to show that even the most severe cases can be analyzed in this extremely fast analytical framework. Take a look at Karttunnen and Beesley's work out of PARC.
FSAs are also a great place to start learning about machine learning concepts like hidden markov models, because in many ways, the problem can be broken down using the same ideas and vocabulary.
于 2008-12-12T22:00:20.650 回答
1
One item that hasn't been mentioned so far is the semantic equivalence of finite state automata and regular expressions. A regular expression can be compiled to a finite state automaton (this is how regex libraries work) and vice-versa.
于 2008-12-12T22:02:02.520 回答
1
FSA (including DFA and NFA) are very important for computer science and they are use in many fields including many fields. For instance hidden markov fields for speech recognition also regular expressions are converted to the FSA's before they are interpreted by the software and NLP (Natural Language Processing), AI (game programming), Robot Programming etc.
One of the disadvantage of FSA's are they are usually slow and usually hard to implement and hard to understand or visualize while reading the code, but they are good because they usually provide generic solutions to the problems and they are well-known with a lot of studies on FSA's.
于 2009-01-03T18:55:44.830 回答