闲聊技术贴，关于状态机
状态机很重要，相当的重要
至少我知道有两个比较好的库，架构的原理都是状态机的原理，OPENGL LUA
运动控制软件当中很多架构也都是基于状态机的架构，或者说在运动控制软件当中没有用到状态机的很少
或许仅仅是你没有意识到而已
而且很多支持脚本的系统也都是基于状态机的
=====================================================================
现在谈状态机，内容不限，随便
大家可以举例现实当中的应用，原理，感想，亦或是其它
======================================================
本人比较关心的是，到底什么才是状态机？
大家可以去看编译原理上讲的状态机，和最开始的纸带存储器的状态机是一样的，但是明显的OPENGL LUA所使用的
状态机的概念又有所不同，这个问题困扰我很久了
=====================================================
今天的话题，只要是基于状态机的，你想谈什么 随便
理解最深最好的那个人100分相送，剩下100分给大家发，不知道我的级别是否还能加分（好像最多是200）如果可以我还会加
[解决办法]
其实我以前想过写出这么一个东西来。
state<UserInfo> _s;
//define state mapping
s.setCondition(lambda, _otherState);
//use the states
Singleton<StateManager>::Instance()->getState(lambda);
其中lambda表示一个表达式，可以是简单的表达式，也可以是一个函数对象什么的。
StateManager帮你维护状态的变迁。
可以实现不？
[解决办法]
有一道acm题:
http://acm.timus.ru/problem.aspx?space=1&num=1102
1102. Strange Dialog
One entity named "one" tells with his friend "puton" and their conversation is interesting. "One" can say words "out" and "output", besides he calls his friend by name. "Puton" can say words "in", "input" and "one". They understand each other perfect and even write dialogue in strings without spaces.
You have N strings. Find which of them are dialogues.
Input
In the first line of input there is one non-negative integer N ≤ 1000. Next N lines contain non-empty strings. Each string consists of small Latin letters. Total length of all strings is no more than 107 characters.
Output
Output consists of N lines. Line contains word "YES", if string is some dialogue of "one" and "puton", otherwise "NO".
如果使用状态机进行解答就相当简单:
#include <stdio.h>void main(){ const int a[] = {0,0,0,0,1,0,0,0,2,0,0,0,0,3,4,5,0,0,0,6,7,0,0,0,0,0}; const int b[][8] = { //* e i n o p t u {15,15, 7,15, 4,11,15,15}, // 0 {15,15, 7,15, 4, 8,15,15}, // 1 {15,15, 7,15,10,11,15,15}, // 2 {15, 0, 7,15, 4,11,15,15}, // 3 {15,15,15, 5,15,15,15, 6}, // 4 {15, 0,15,15,15,15,15,15}, // 5 {15,15,15,15,15,15, 1,15}, // 6 {15,15,15, 1,15,15,15,15}, // 7 {15,15,15,15,15,15,15, 9}, // 8 {15,15,15,15,15,15, 2,15}, // 9 {15,15,15, 3,15,15,15, 6}, // 10 {15,15,15,15,15,15,15,12}, // 11 {15,15,15,15,15,15,13,15}, // 12 {15,15,15,15,14,15,15,15}, // 13 {15,15,15, 0,15,15,15,15} // 14 }; int c, n, s; scanf("%d\n", &n); while (n--) { for (s = 0; (c = getchar()) != 10;) if (s < 15) s = b[s][a[c - 97]]; printf(s < 4 ? "YES\n" : "NO\n"); }}
[解决办法]
状态机是一个非常有意思的主题。他可以非常简单，也可以非常复杂。最简单的一个指示变量就可以叫做一个状态机，这也是我们最常用的。但是一旦遇到复杂的情况，这种方式就力不从心了，最终的结果就是到处是状态变量，到处是条件判断，导致程序难以维护，耦合度极高。
一般的应用用不到复杂的状态机，所以我们平时见到的复杂的状态机比较少。编译器算是我们最容易想到的复杂状态机应用。我经历过一个项目其中也用到了比较复杂的状态机，这是一个UI项目，使用WPF和MVVM架构设计。前端UI绑定到逻辑层上暴露的数据接口，逻辑层内部实现了一个状态机，是用Enterprise Architect先画出状态机，然后转化成代码。使用该状态机，实现了各种输入和输出之间的解耦。建议想熟悉状态机设计的人去参考一下Enterprise Architect的状态机设计，结合具体的项目，一定受益匪浅。
[解决办法]
惭愧啊，对软件框架我没有了解，所以说不出什么来。
我只是在实际做题中用到了状态机，觉得这个例子不错，短小、精简、高效，所以拿出来献丑了，见笑。
另外，字符串匹配中著名的KMP(Knuth-Morris-Pratt)算法也是利用状态机的，这已经是相当成熟的算法了，用KMP做关键字在网上一搜一大堆，就不再多说了。
[英]罗杰·彭罗斯的《皇帝新脑》第二章 算法和图灵机，其中论述的“普适图灵机”也相当有意思，也涉及到状态机的概念。
[解决办法]
复杂状态机的设计大体有两种方法，一种是表格映射，即把状态抽象为一个表格，表格中的每个元素定义了状态的跃迁规则。另一种是面向对象方法，即把所有状态抽象为一个个的对象，内部定义了状态的跃迁规则，并有事件触发规则等等来跟外界交互，上面说的Enterprise Architect设计的状态机就属于这种。这里只能这样简单介绍了，具体的要自己做一些具体的项目来体会。
[解决办法]
这话题还真大！
状态机的应用太广了，
个人觉得编译和人工智能领域用的最多。
去年看了些关于抽象状态机(Abstract State Machines,ASM)的东西。主要应用于软件规约。可以看看微软的AsmL，可以在Word中直接使用。ASM应该算是软件领域比较前沿的东西。
抽象状态机的基本思想可以追溯到上个世纪80年代.ASM的发明者Yuri Gurevich从数学领域转到计算机领域发现这样的现象:一个程序语言在不同的编译器下有着不同的编译.这就存在一个问题:究竟一个程序语言的确切语义是什么?
为了上面的问题,Yuri Gurevich进行研究的初衷是:(1)为Church.Turing论题引入资源边界的限制;(2)采用动态结构(Dynamic structures)定义更为抽象的计算设备.Yuri Gurevich从数学中得到了启迪,任何静态的数学实体,都可以表示为一阶结构,因而算法的每个状态为一阶结构.计算(Computation)就是状态的进化(Evolving).可以容易的用一个函数来表示一个关系,使得一阶结构中可以只含有函数,而只有函数运算的结构在泛代数(Universal Algebras)中称为代数.因此这种模型最初被分别称为动态结构(Dynamic Structures),动态代数(Dynamic Algebras),以及进化代数(=Evolving Algebras).最终,通过多年的研究,人们发现进化代数实际上是Dj.jl(stra的抽象机(Abstract Machine)的基本概念和利用Tarski的结构作为一般的抽象状态(Abstract States)的基本思想的完美结合,最终称为抽象状态机.所以ASM=Abstract State+Abstract Machine.
目前,ASM已经从一种思想发展成一种成熟的模型,一种语言,一种被国际标准化组织承认的、在软件和硬件规约中广泛使用的工具.同时ASM的工业用软件开发环境已经初露端倪,并且已经得到成功的运用.值得一提的是,在Microsoft的大力支持和推动下,已经产生了ASM Language(即AsmL并整合到了.Net开发环境中.
[解决办法]
ASML主要用于软件开发前的模型测试
http://research.microsoft.com/en-us/projects/asml/
[解决办法]
我以前写过一篇文章，讨论状态机在IVR设计中的应用，当然，我是否定它的，拙文在这里，“从历史角度再论‘状态机’”：
http://blog.csdn.net/bluesen/archive/2006/05/18/744749.aspx
[解决办法]
状态机属于计算理论的范畴，lz可以去看看相关的书籍，从最简单的DFA到TM，状态机总是与它的输入及语言相关，这都是在一块儿的，关于这方面的知识我推荐一本书《计算理论导引》，翻译的很好，习题也很好。
[解决办法]
状态机（FSM）在通信系统协议方面应用最为广泛
[解决办法]
我也来一个用DFA解决一个ACM中的计数问题的代码
在只有一个数字和有两个数字的情况下用了不同的算法
后者是用DFA
Description
A positive number M contains another number N, when N is a substring of M in decimal.
Such as 12 contains 12; 121 contains 12; 213 contains 13; but 102 doesn't contain 12.
Now given a positive N, just calculate the number of all the numbers that contain N in [a,b].
Input
There are several test cases,each contains three numbers:N,a,b( 1 ≤ N < 100,1 ≤ a < b ≤ 2^30).
Output
The number of the numbers.
Sample Input
13 13 1350
Sample Output
84
Source
htam60@joj
#include <iostream>#include <deque>#include <queue>#include <vector>#include <string>#include <map>#include <set>#include <list>#include <algorithm>#include <functional>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>using namespace std;#define FILL(a, v) memset(a, v, sizeof(a))#define FILLN(a, v, n) memset(a, v, sizeof(a[0]) * n)#define INPUT1(x) int x;scanf("%d", &x)#define INPUT2(x, y) int x, y;scanf("%d%d", &x, &y)#define INPUT3(x, y, z) int x, y, z;scanf("%d%d%d", &x, &y, &z)#define INPUTARRAY(arr, begin, end) for (int i = begin; i < end; ++i) scanf("%d", arr+i);#define FOR(v, begin, end) for (int v = begin; v < end; ++v)#define FORTO(v, begin, last) for (int v = beign; v <= last; ++v)#define FORDOWNTO(v, begin, last) for (int v = begin; v >= last; --v)#define FOREVER for (;;)#define TWO(i) (1<<i)typedef long long int64;inline int ExistSingle(int n, int x){ int dig[15], curr = 0, last = 0; int t = n; for (; n; n /= 10) { int d = n % 10; if (d < x) dig[curr++] = d; else if (d > x) dig[curr++] = d-1; else { dig[curr] = d-1; for (; last < curr; ++last) dig[last] = 8; ++curr; } } int ans = 0, b = 1; for (int i = 0; i < curr; ++i) { ans += dig[i] * b; b *= 9; } return t - ans;}int solve_single(int n, int beg, int end){ return ExistSingle(end, n) - ExistSingle(beg-1, n);}inline int ExistDouble(int n, int (*dfa)[10], int (*cnt)[3]){ if (n < 10) return 0; int dig[15], len = 0; for (; n; n /= 10) dig[len++] = n % 10; --len; int ans = 0; int state = 0; for (; len >= 0; --len) { FOR (j, 0, dig[len]) ans += cnt[len][dfa[state][j]]; state = dfa[state][dig[len]]; } return ans + cnt[state][0];}int solve_double(int n, int beg, int end){ int first = n / 10, second = n % 10; int dfa[3][10] = {0}; for (int i = 0; i < 10; ++i) dfa[2][i] = 2; dfa[0][first] = 1, dfa[1][second] = 2; if (first != second) dfa[1][first] = 1; int cnt[13][3] = {0}; cnt[0][2] = 1; FOR (i, 1, 12) FOR (j, 0, 3) FOR (k, 0, 10) cnt[i][j] += cnt[i-1][dfa[j][k]]; return ExistDouble(end, dfa, cnt) - ExistDouble(beg-1, dfa, cnt);}int main(){ int n, i, j; while (scanf("%d%d%d", &n, &i, &j) == 3) { if (n < 10) printf("%d\n", solve_single(n, i, j)); else printf("%d\n", solve_double(n, i, j)); } return 0;}
[解决办法]
晕，其实看了这个标题我下意识想起的全部都是硬件结构，我不是学计算机的，我学的是IC设计。
最早接触状态机是在数字电路设计这门课程里，设计的状态机最终结构是门级结构，当然也可以优化到晶体管级。
我也没有用C或者其他高级语言实现过状态机，或者说可能实现过但是我并不把高级语言实现的程序叫做状态机。
我理解的状态机就是一种时序电路结构。
要实现状态机必然有状态的存储和转换，这就要求使用时序电路最基本的组件：触发器，这正是所谓“上升沿触发”“下降沿触发”的根源所在，因为触发器的结构决定了同步状态机到底是在上升沿还是下降沿触发。
写FPGA时我用的是Verilog 这种硬件描述语言里也有和C一样的case语句，当满足一定得语法描述的时候，综合器（相当于软语言的编译器）就会将硬件实现为状态机，所以搞过FPGA之后再结合对C的理，其实具有多级连续条件判断的程序结构都可以被理解为广义状态机。当然在数字电路里，状态机具有明确的数学定义，比如设计时应当把所有的状态的下一状态有合适的定义以避免进入死循环。我理解数字电路里的状态机主要用于条件判断还有有严格顺序和时间要求的场合，比如FPGA控制外部AD采样，就可以用状态机实现严格的AD时序。
在程序中也是一样，我觉得最好的例子可能是游戏中的NPC，不考虑人工智能的前提下，NPC只能根据预设好的条件和用户的反馈做出回应，也就是可以这样说，NPC有n个状态，用回每回应一次就是一个“上升沿”（一次触发），NPC根据用户的选择从当前第k个状态跳转至第m个状态，当然状态跳转的范围是在n以内。开发人员要做的就是在某个状态让玩家去做相应的事比如：获得宝物、触发任务、升级等等。而实现这种结构的基本框架可能是switch...case...
不是做软件开发的，呵呵，理解的和大家有所不同，其实状态机这个概念软硬均可实现，只要是能很好的服务于应用，为什么不应用呢？