Erm - what the question said. It's something I keep hearing about, but I've not got round to looking into it yet.
嗯 - 问题是什么。这是我一直听到的,但我还没有完成调查。
(updated) I could look up the definition... but why not (as pointed out by @erikson) get insight into your real experiences and anecdotes. Community Wiki'd incase that helps folks vote up the most insightful answer. Interesting reading so far, thanks!
(更新)我可以查找定义......但为什么不(正如@erikson指出的那样)深入了解你的真实经历和轶事。社区维基会帮助人们投票给最有见地的答案。有趣的阅读到目前为止,谢谢!
12 个解决方案
#1
13
Short answer, it is a technique that you can use to express systems with concrete states (as opposed to quantum states / probability distributions).
简而言之,这是一种可用于表达具体状态系统的技术(与量子态/概率分布相对)。
Quoting the 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.
有限状态机(FSM)或有限状态自动机(复数:自动机)或简称状态机,是由有限数量的状态,这些状态之间的转换和动作组成的行为模型。有限状态机是具有原始内部存储器的机器的抽象模型。
So, what does that mean to you? Put simply, it is an effective way to represent the path(s) from a starting state to the end state(s) of the system that you care about. Using regular expressions as a fairly easy to understand example, let's look at the pattern AB+C (imagine that that plus is a superscript). I would expect to this pattern to accept strings such as "ABC", "ABBC", "ABBBC", etc. A at the start, C at the end, some number of B's in the middle (greater than or equal to one).
那么,这对你意味着什么?简而言之,它是一种有效的方式来表示从您关注的系统的起始状态到最终状态的路径。使用正则表达式作为一个相当容易理解的例子,让我们看一下AB + C模式(假设这个加号是上标)。我希望这种模式能够接受诸如“ABC”,“ABBC”,“ABBBC”等字符串.A在开始时,C在结尾处,中间有一些B(大于或等于1) 。
If you think about it, it's almost easier to think about this in terms of a picture. Faking it with text (and that my parentheses are a loopback arc), you can see that A (on the left), is the starting state and C (on the right) is the end state on the right.
如果你考虑一下,从图片的角度考虑这个几乎就容易了。用文本伪造它(我的括号是一个环回弧),你可以看到A(在左边)是起始状态,C(在右边)是右边的结束状态。
_
( )
A --> B --> C
From FSAs, you can continue your journey into computational complexity by heading over to the land of Turing Machines.
从FSA,您可以前往图灵机的土地,继续您的计算复杂性之旅。
However, you can also use state machines to represent real behaviors and systems. In my world, we use them to model certain workflow of actual people working with components that are extremely intolerant of mistakes in state order. As in, "A had better happen before C or there will be a very serious problem. Make that be not possible right now."
但是,您也可以使用状态机来表示真实的行为和系统。在我的世界中,我们使用它们来模拟实际人员的某些工作流程,这些工作人员使用非常不容忍状态错误的组件。就像在“,A最好在C之前发生,或者会有一个非常严重的问题。现在就不可能做到这一点。”
#2
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.)
事实证明,你可以用数学方式看待这样的机器,并发现有些东西可以做但不能做。正则表达式基本上是一种描述有限状态机的方法,其中状态是一组不同的字符串,并且规则根据下一个字符读取将您从一个状态移动到另一个状态。你可以证明这一点。但是你也可以证明没有有限状态机可以判断表达式中的括号是否匹配(通过FSA的泵浦引理)。
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.
您应该了解FSA的原因是它们可以用来解决许多问题:字符串匹配,系统控制,业务流程描述,数字电路设计。他们本身就很漂亮。
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.
形式上,FSA是代数结构F =ΣΣ,S,s0,F,δ⟩其中Σ是输入字母,S是一组状态,s0∈S是特定的开始状态,F⊆S是一组接受状态,δ:S×Σ→S是状态转移函数。
#3
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!
在OOP术语中:如果你有一个对象,你调用某些事件的方法,以及一些(其他)方法具有不同的行为取决于以前的调用....惊喜!你有一台状态机!
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
如果你不了解这个理论你会想一段时间,写一些聪明的黑客,并得到一些难以解释和记录的东西...因为你没有用它来描述它的话
#4
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.
由于Web服务通常不具有状态,因此您通常不会在Web服务中看到这一点 - 您重新排列URL,以便每个URL对应于代码中的单个路径。
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.
我想另一种思考方式可能是每个Web服务器都是一个FSM,状态信息保存在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.
通常,FSM被实现为切换变量的switch语句。每个案例都是不同的州。在案例结束时,您可以将状态设置为新值。你几乎肯定在某个地方见过这个。
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.
FSM的优点在于,您可以将状态作为数据的一部分而不是代码。想象一下,您需要在数据库中填写1000个项目。传入的数据将处理1000个项目中的一个,但您通常没有足够的数据来完成操作。
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.
如果没有FSM,您可能会有数百个线程等待其余数据,以便完成处理并将结果写入数据库。使用FSM,您将状态写入DB,然后退出线程。下次您可以检查传入的数据,从线程中读取状态,这应该为您提供足够的信息来确定要运行的代码。
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.
几乎每个FSM操作都可以通过专用线程来完成,但可能不是很好(复杂性基于状态数倍增,而对于状态机,复杂性的增加更加线性)。此外,还有一些概念设计问题 - 在某些情况下检查状态级别的代码比在代码级别检查代码要容易得多。
#5
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:
上面的好答案。我只想补充一点,FSA主要是一种思考工具,而不是编程技术。使它们有用的是它们具有良好的属性,并且任何具有这些属性的东西都具有这些属性。如果您可以将某些事物视为FSA,那么您可以通过多种方式构建它:
-
as a regular expression
作为正则表达式
-
as a state-transition table
作为状态转换表
-
as a while-switch-on-state loop
作为一个while-switch-on-state循环
-
as a goto-net (horrors!)
作为goto-net(恐怖!)
-
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.
如果有人说某事是FSA,你可以立即知道他们在谈论什么,无论它是如何构建的。
#6
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:
一个典型的例子是游戏AI,其中NPC具有根据玩家所在位置而改变的不同状态,例如:
- NPC_STATE_IDLE
- NPC_STATE_ALERT (player at less than 100 meters)
- NPC_STATE_ENGAGE (player attacked NPC)
- NPC_STATE_FLEE (low on health)
NPC_STATE_ALERT(球员不到100米)
NPC_STATE_ENGAGE(玩家攻击NPC)
NPC_STATE_FLEE(健康状况不佳)
where a FSM can describe easily the transitions and help perform complex reasoning about the system the FSM is describing.
FSM可以轻松描述转换并帮助执行有关FSM描述的系统的复杂推理。
#7
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.
如果您是一名“视觉”学习者,这里有一个很好的链接,可以提供非常容易理解的介绍。
Oliver Steele的Reanimator
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)
(注意:该链接指向正则表达式上下文中对DFA和NDFA的讨论 - 使用动画交互图)
#9
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.
这是一个非常常见的工具,并且知道理论基础知识,能够对其进行推理并且知道如何将两个FSM组合成一个完成相同工作的单个FSM可以是一个很大的帮助。
#10
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.
FSA是很好的数据结构,因为你必须实现它们,所以你在Chomsky层次结构的最低计算复杂度上工作。一个很好的例子是单词形态学(单词的各个部分如何组合在一起)。已经做了大量工作来证明即使是最严重的病例也可以在这个极其快速的分析框架中进行分析。看看Karttunnen和Beesley在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.
FSA也是开始学习机器学习概念(如隐马尔可夫模型)的好地方,因为在很多方面,问题可以使用相同的想法和词汇来分解。
#11
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.
到目前为止尚未提及的一个项目是有限状态自动机和正则表达式的语义等价。正则表达式可以编译为有限状态自动机(这是正则表达式库的工作方式),反之亦然。
#12
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.
FSA(包括DFA和NFA)对计算机科学非常重要,它们可用于许多领域,包括许多领域。例如,用于语音识别的隐马尔可夫字段也可以在软件和NLP(自然语言处理),AI(游戏编程),机器人编程等解释之前将正则表达式转换为FSA。
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.
FSA的一个缺点是它们通常很慢并且通常难以实现,并且在阅读代码时难以理解或可视化,但它们很好,因为它们通常提供通用的解决方案来解决问题,并且它们在很多方面都是众所周知的。关于FSA的研究。
#1
13
Short answer, it is a technique that you can use to express systems with concrete states (as opposed to quantum states / probability distributions).
简而言之,这是一种可用于表达具体状态系统的技术(与量子态/概率分布相对)。
Quoting the 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.
有限状态机(FSM)或有限状态自动机(复数:自动机)或简称状态机,是由有限数量的状态,这些状态之间的转换和动作组成的行为模型。有限状态机是具有原始内部存储器的机器的抽象模型。
So, what does that mean to you? Put simply, it is an effective way to represent the path(s) from a starting state to the end state(s) of the system that you care about. Using regular expressions as a fairly easy to understand example, let's look at the pattern AB+C (imagine that that plus is a superscript). I would expect to this pattern to accept strings such as "ABC", "ABBC", "ABBBC", etc. A at the start, C at the end, some number of B's in the middle (greater than or equal to one).
那么,这对你意味着什么?简而言之,它是一种有效的方式来表示从您关注的系统的起始状态到最终状态的路径。使用正则表达式作为一个相当容易理解的例子,让我们看一下AB + C模式(假设这个加号是上标)。我希望这种模式能够接受诸如“ABC”,“ABBC”,“ABBBC”等字符串.A在开始时,C在结尾处,中间有一些B(大于或等于1) 。
If you think about it, it's almost easier to think about this in terms of a picture. Faking it with text (and that my parentheses are a loopback arc), you can see that A (on the left), is the starting state and C (on the right) is the end state on the right.
如果你考虑一下,从图片的角度考虑这个几乎就容易了。用文本伪造它(我的括号是一个环回弧),你可以看到A(在左边)是起始状态,C(在右边)是右边的结束状态。
_
( )
A --> B --> C
From FSAs, you can continue your journey into computational complexity by heading over to the land of Turing Machines.
从FSA,您可以前往图灵机的土地,继续您的计算复杂性之旅。
However, you can also use state machines to represent real behaviors and systems. In my world, we use them to model certain workflow of actual people working with components that are extremely intolerant of mistakes in state order. As in, "A had better happen before C or there will be a very serious problem. Make that be not possible right now."
但是,您也可以使用状态机来表示真实的行为和系统。在我的世界中,我们使用它们来模拟实际人员的某些工作流程,这些工作人员使用非常不容忍状态错误的组件。就像在“,A最好在C之前发生,或者会有一个非常严重的问题。现在就不可能做到这一点。”
#2
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.)
事实证明,你可以用数学方式看待这样的机器,并发现有些东西可以做但不能做。正则表达式基本上是一种描述有限状态机的方法,其中状态是一组不同的字符串,并且规则根据下一个字符读取将您从一个状态移动到另一个状态。你可以证明这一点。但是你也可以证明没有有限状态机可以判断表达式中的括号是否匹配(通过FSA的泵浦引理)。
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.
您应该了解FSA的原因是它们可以用来解决许多问题:字符串匹配,系统控制,业务流程描述,数字电路设计。他们本身就很漂亮。
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.
形式上,FSA是代数结构F =ΣΣ,S,s0,F,δ⟩其中Σ是输入字母,S是一组状态,s0∈S是特定的开始状态,F⊆S是一组接受状态,δ:S×Σ→S是状态转移函数。
#3
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!
在OOP术语中:如果你有一个对象,你调用某些事件的方法,以及一些(其他)方法具有不同的行为取决于以前的调用....惊喜!你有一台状态机!
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
如果你不了解这个理论你会想一段时间,写一些聪明的黑客,并得到一些难以解释和记录的东西...因为你没有用它来描述它的话
#4
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.
由于Web服务通常不具有状态,因此您通常不会在Web服务中看到这一点 - 您重新排列URL,以便每个URL对应于代码中的单个路径。
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.
我想另一种思考方式可能是每个Web服务器都是一个FSM,状态信息保存在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.
通常,FSM被实现为切换变量的switch语句。每个案例都是不同的州。在案例结束时,您可以将状态设置为新值。你几乎肯定在某个地方见过这个。
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.
FSM的优点在于,您可以将状态作为数据的一部分而不是代码。想象一下,您需要在数据库中填写1000个项目。传入的数据将处理1000个项目中的一个,但您通常没有足够的数据来完成操作。
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.
如果没有FSM,您可能会有数百个线程等待其余数据,以便完成处理并将结果写入数据库。使用FSM,您将状态写入DB,然后退出线程。下次您可以检查传入的数据,从线程中读取状态,这应该为您提供足够的信息来确定要运行的代码。
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.
几乎每个FSM操作都可以通过专用线程来完成,但可能不是很好(复杂性基于状态数倍增,而对于状态机,复杂性的增加更加线性)。此外,还有一些概念设计问题 - 在某些情况下检查状态级别的代码比在代码级别检查代码要容易得多。
#5
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:
上面的好答案。我只想补充一点,FSA主要是一种思考工具,而不是编程技术。使它们有用的是它们具有良好的属性,并且任何具有这些属性的东西都具有这些属性。如果您可以将某些事物视为FSA,那么您可以通过多种方式构建它:
-
as a regular expression
作为正则表达式
-
as a state-transition table
作为状态转换表
-
as a while-switch-on-state loop
作为一个while-switch-on-state循环
-
as a goto-net (horrors!)
作为goto-net(恐怖!)
-
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.
如果有人说某事是FSA,你可以立即知道他们在谈论什么,无论它是如何构建的。
#6
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:
一个典型的例子是游戏AI,其中NPC具有根据玩家所在位置而改变的不同状态,例如:
- NPC_STATE_IDLE
- NPC_STATE_ALERT (player at less than 100 meters)
- NPC_STATE_ENGAGE (player attacked NPC)
- NPC_STATE_FLEE (low on health)
NPC_STATE_ALERT(球员不到100米)
NPC_STATE_ENGAGE(玩家攻击NPC)
NPC_STATE_FLEE(健康状况不佳)
where a FSM can describe easily the transitions and help perform complex reasoning about the system the FSM is describing.
FSM可以轻松描述转换并帮助执行有关FSM描述的系统的复杂推理。
#7
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.
如果您是一名“视觉”学习者,这里有一个很好的链接,可以提供非常容易理解的介绍。
Oliver Steele的Reanimator
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)
(注意:该链接指向正则表达式上下文中对DFA和NDFA的讨论 - 使用动画交互图)
#8
#9
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.
这是一个非常常见的工具,并且知道理论基础知识,能够对其进行推理并且知道如何将两个FSM组合成一个完成相同工作的单个FSM可以是一个很大的帮助。
#10
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.
FSA是很好的数据结构,因为你必须实现它们,所以你在Chomsky层次结构的最低计算复杂度上工作。一个很好的例子是单词形态学(单词的各个部分如何组合在一起)。已经做了大量工作来证明即使是最严重的病例也可以在这个极其快速的分析框架中进行分析。看看Karttunnen和Beesley在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.
FSA也是开始学习机器学习概念(如隐马尔可夫模型)的好地方,因为在很多方面,问题可以使用相同的想法和词汇来分解。
#11
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.
到目前为止尚未提及的一个项目是有限状态自动机和正则表达式的语义等价。正则表达式可以编译为有限状态自动机(这是正则表达式库的工作方式),反之亦然。
#12
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.
FSA(包括DFA和NFA)对计算机科学非常重要,它们可用于许多领域,包括许多领域。例如,用于语音识别的隐马尔可夫字段也可以在软件和NLP(自然语言处理),AI(游戏编程),机器人编程等解释之前将正则表达式转换为FSA。
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.
FSA的一个缺点是它们通常很慢并且通常难以实现,并且在阅读代码时难以理解或可视化,但它们很好,因为它们通常提供通用的解决方案来解决问题,并且它们在很多方面都是众所周知的。关于FSA的研究。