2007年1月31日、有限状态机与有限状态自动机

在前段时间学习编译原理的时候。就对有限状态自动机不是很了解。导致在看到后面的时候概念混乱而看不明白，最后 放弃先看离散数学，今天学到了离散数学最后一个基本知识点也是对我来说最重要的一个知识点：有限状态机。以下是有关有限状态机的一些概念：    有限状态机是具有基本内部记忆的抽象机模型。有限状态自动机是特殊类型的有限状态机。    首先需要知道延迟的概念：一个单位时间延迟在时刻t接受一位输入x1，且输出x2，它是在t时刻之后的t-1时刻作为输入接受的一位。可以理解为在时刻t进行的操作为：接受一位x1，在这时刻处理后输出x2，输出的数作为该时刻之后的时刻的输入数。    对有限状态机的定义：有限状态机是具有一个基本内部记忆的抽象机器模型，定义如下： font size="2">可以这么理解吧：对于有限状态机来说，包括有：一个输入的符号集合、一个输出的符号集合与有限状态集合，最后还有一个状态处理四部分。而在状态处理这部分中，包括有一个有限的状态与输入符号集合的对应关系即函数，还包括一个该有限状态与输出符号集合的对应关系，即输出函数，这样就是一个有限状态机的组成。    对于有限状态机的描述可以绘制转换图如：

的转换图为：

 

关于绘制转换图的方法大致如下：首先从状态0开始，当对对于输入a的情况下，找出函数f的关系可以画出当输入a的时候状态由0的变化，然后两个结点之间连上边（状态为结点，边为关系），并对这样的输入与转变的状态在函数g下的值添写在边上，如上：b/0。由此往返，则可以绘制全部的转换图。 关于有限状态自动机的定义为：对于一个有限状态自动机是一个有限状态机，输出符号的集合是{0，1}并且当前的状态决定最后的输出，最后输出为1的状态为接收状态。 对于如上转换图，如果在状态0最后输出是0，而在状态1或2，最后输出为1，于是这个有限状态机为有限状态自动机，接收状态为1和2。（注：所有输出为1，表示输出1标记它的进入边，即用进入边考虑。）对于有限状态自动机的状态图则可以用双圆代替接收状态的结点。

对于有限状态自动机的定义：

 

与有限状态机的定义对比：首先有限状态自动机的输出符号已知，另一个知道了接收状态的集合，就可以定义出有限状态自动机的组成了，对于它的状态图就很好画了。 语言和文法 语言定义：设A是有限集合，A 上的语言L是A 上所有字符串的集合A*的子集（A*表示A 上所有元素的结合，如A为{a，b}则A*可以是ab,a,b,abbb,aaab等等） 短语文法的组成：一个有限非终结符号集合N，一个有限终结符号集合T其中这两个集合交为空，而{N交T}*-T*} ，（U交T）*的一个有限子集P，称为产生式集合，并有一个开始符号，属于N。产生式（A，B）写为A àB，其中A 至少包括一个非终结符号，而B可以包括非终结符号和终结符号的任意组合。 定义：  

 

可以理解为上下文有关文法中，A推出B的情况下，B 可以是U并T中的任意字符组合的形式，除了空串，而上下文武官文法中，B 的情况可以为空串形式，也就是说在最后的推导过程中，可以产生空串而进行推导。可以这么说吧：一个正则文法是上下文无关文法，不具有形式为A推导为空的产生式的上下文无关文法就是上下文有关文法。 非确定有限状态自动机 非确定有限状态自动机与有限状态自动机的区别在于有限状态自动机中，下个状态函数引导到唯一的状态，而不确定有限状态自动机中，下一个函数引导的是状态集合。也就是说在有限状态自动机的定义上。仅仅在下个函数定义那里，改为f引导的结果为一个集合。  

有关的基本概念已经看完了。大体上理解还可以，虽然不能跟以前学数学那样去证明书中的理论，但是对基本概念还算是有个了解了。下来该重新看编译原理，如果再碰到有基本地方不明白的话。就仅仅需要查看书中概念即可。明天开始编译原理的学习。