全部博文(413)
分类: LINUX
2011-12-23 16:01:16
转载时请注明出处和作者联系方式
文章出处:http://www.limodev.cn/blog
作者联系方式:李先静
系统程序员成长计划-文本处理(一)
状态机(1)
o 有穷状态机的形式定义
有穷状态机是一个五元组 (Q,Σ,δ,q0,F),其中:
Q是一个有穷集合,称为状态集。
Σ是一个有穷集合,称为字母表。
δ: Q xΣQ称为状态转移函数。
q0 是初始状态。
F 是接受状态集。
教科书上是这样定义有穷自动机的,这个形式定义精确的描述了有穷状态机的含义。但是大部分人(包括我自己)第一次看到它时,反复的读上几遍,仍然不知道它在说什么。幸好通过一些实例,我们可以很容易明白有穷状态机的原理。
自动门是一个典型的有穷状态机:
它有“开”和“关”两种状态,这就是它的状态集,也就是上面所说的Q。
人可以从自动门进来或出去,当人进来或出去的时候,自动门会自动打开,如果在规定的时间内没有人进出,自动门会自动关上。人的进来、出去和超时三个 事件是自动门的字母表,也就是上面所说的Σ。而自动门在当前状态下,对事件的响应,会引起状态的变化,这就是状态转换函数,也就是上面所说的δ。
自动门刚安装好的时候,我们可以认为它是关上的,所以关闭状态是自动门的初始状态。
在理想情况下,自动门会一直运行,所以它没有接受状态,接受状态集F是空集。
有穷状态机的形式定义很精确,文字描述比较通俗,而图形表示则比较直观。通用建模语言(UML)里的状态图是状态机的常用图形表示方法。简单的状态 图包括一些状态,用圆角方框表示,里面有状态的名称。状态之间的转换,用箭头表示,上面可以加转换条件。自动门的状态机可以用下图表示:
有穷状态机很简单,在生活中可以找出很多这样的例子。但是教科书里讲得太复杂了,一会儿证明确定性有穷状态机和非确定性有穷状态机的等价性,一会儿 证明正则表达式的正则运算是封闭的,一会儿又来个泵引理。花了很长时间,我才明白这些原理,但两年之后,我又把它们忘得一干二净。
主要原因是工作中没有机会运用它们,这些理论的证明于编程没有太大用处,不过状态机本身却是文本处理利器,由于程序员在很多场合下都是在与文本数据 打交道,所以状态机是程序员必备的工具之一。这里我们将一起学习如何用状态机来处理文本数据,后面我们也会提到状态机的其它用途,不过不是本节的重点。