关于SM的一些提示
正则表达式（RegularExpression），表示字符串的格式[2]。
ARegularExpressionisbuiltupoutofsimplerregularexpressionsusingasetofdefiningrules[1].
正则表达式完全由它匹配的串集来定义，这个串集称为由正则表达式生成的语言（languagegeneratedbytheregularexpression）[2]。
上述关于正则表达式的定义摘自编译原理的书上。正则表达式确实不容易定义，即使你一看就知道rm*.o（删除以.o结尾的所有文件）这用到了正则表达式，egrep^a.*n$*.cc（在以.cc结尾的所有文件中查找以a开头以n结尾的行）这也用到了正则表达式。
综合一下上述关于正则表达式的定义：正则表达式是一套规则集，通过这一套规则集，可以生成串集（由正则表达式生成的语言），通过规则集可以方便表达、定义和匹配串集。
正则表达式可以构造成等价的非确定性有穷自动机。
NFA[1]由字符表，状态集，转换函数，初始状态（一个初始状态），以及接受状态的集合（可以多个接受状态）组成。转换函数接受字符，转换状态。一系列转换函数从初始状态到接受状态生成字符串，这些字符串构成NFA确定的串集。
DFA[1]首先是NFA，但是其中没有空串转换（不需要输入字符，状态从一种状态迁移到另外一种状态）；也不存在多重转换（一个输入字符，会转换到多个状态）。
NFA不容易用计算机程序来实现。可以用子集构造法把NFA转变为DFA。背后的原理是，DFA的每个状态由NFA的状态集构成。理论上说，DFA的状态数随NFA的状态数呈指数级增长。但实践中，这种最坏的情况很少发生。
定义三种操作：
状态的空串闭包E-closure(s)：从状态s经0或多个空串(E)能够到达的NFA状态集（包括状态s自身）。
状态集的空串闭包E-closure(T)：状态集T中所有状态s的E-closure(s)的并集。
状态集的迁移闭包move(T,a)：状态集T中的状态经字符a能够到达的NFA状态集。
NFA由状态集合(Nstates)和状态转换表[Ntable(s,a)=s1]组成，把NFA转换为DFA，我们构造出等价的状态集合(Dstates)和状态转换表[Dtable(s,a)=s1]即可。下面的伪码描述这样的过程。
initiallyE-closure(s0)istheonlystateinDstatesanditisunmarked
whilethereisaunmarkedstateTinDstatesdobegin
markT
foreachinputsymboladobegin
U=E-closure(move(T,a))
ifUisnotinDstatesthen
addUasanunmarkedstatetoDstates
Dtable(T,a)=U
end
end
SM是软件开发中被经常用到的技术。在通信系统中，在售票系统中。在UML中就有专门的StateMachineDiagram[3]用来描述SM。SM图由状态(State)和转换(Transition)组成，包括一些前置条件(Preconditioin)，行为(Action)等。正则表达式，DFA，NFA，这些编译原理中的技术可以用于SM的构建。
在实现SM的过程中，涉及状态转换，涉及不同状态的不同行为，如果这些都用条件判断语句(iforswitch)来实现，会降低代码的可读性，扩展性。因为SM应用如此普遍，在软件开发中构建SM形成了模式。在GangofFour的DesignPatterns[4]中，提到了一种基于查表的方法和详细介绍了State模式。两种方法各有优缺点。共同点是减少了条件判断语句。State模式强调不同状态的行为，查表法更关注定义状态的转换。Refactoring[5]中就建议ReplaceConditionalwithPolymorphism，State模式就是符合这条建议的模式。个人建议采用现代的面向对象语言开发，则选State模式，采用传统的面向过程的语言开发，则可考虑查表法。
在基于查表的方法中，一张二维表(一维是状态，一维是输入)映射了某个状态接受某个输入转换到某个后续状态（输出可以是状态也可以是处理函数的指针）。
在State模式中，对象会在运行时改变State，State改变行为也会改变。定义会改变状态的对象为Context，Context中会包括一个抽象State对象。抽象State中定义了特定状态的行为接口。ConcreteState是State的子类，在其中实现特定状态的行为。SM--StateMachine[1]CompilersPrinciplesTechniquesandTools[2]编译原理及实践
[3]UMLDistilled
[4]DesignPatterns
[5]Refactoring