第3章 有穷自动机
继文法的一般理论之后,本章引入语言的另一种表示形式——有穷自动机。虽然有穷自动机是所有自动机中*简单的一种,它表示语言的能力是有限的,但是它构造简单,在生产和生活中都有它的原型,因此它在计算机科学技术和其他学科中都有广泛的应用。掌握了有穷自动机的基本概念,将为后面学习其他更复杂的自动机打下良好的基础。
3.1 非形式化描���
在客观世界中,具有有穷多个状态的系统比比皆是。例如,日常用的指针式钟表就是一种有穷状态系统,它共有12×60×60个状态,秒针每走一步,系统就从一种状态转移到另一种状态。一局棋也是一种有穷状态系统,如围棋共有3(361)个状态,棋手每走一步,就从一种状态转移到另一种状态。在工业产品中,也有很多类似的例子。比如,电梯的控制结构就是有穷状态系统的一个典型例子。电梯停在每一楼层作为一个状态,它的控制系统不必记住以前的所有动作,而只要知道现在的位置以及用户给出的信号就可以通过改变它的状态(上或下)来满足用户的要求。某些电子产品中的开关电路,是有穷状态系统的又一实际例子。一个开关电路由有穷多个门电路组成,每个“门”可以处于两种状态——开和关(通常记为1和0)之一。具有n个门的开关网络有2(n)种状态,根据输入的信号可以从一种状态变为另一种状态。为了更清楚地说明实际生活中存在的有穷状态系统,我们简单介绍一个电子商务方面的例子。
电子商务在日常生活中的一个应用就是网上购物,这里涉及三个互相关联的方面——顾客、商店和银行。为简单起见,假设只有一个顾客(而且只有一次购物活动),他已在银行建立了账户。假设商店也在银行建立了账户。顾客可以决定把账户上的钱传送给商店以购买商品,然后商店从银行拿到这笔钱并送货给顾客。而且,顾客可以在一定时间内选择取消购物。也就是说,顾客可以告诉银行不再用这笔钱付购物款。因此,三方之间的交互限于以下五种事件:
(1)顾客决定付款购物。顾客告诉商店购买某种物品,并附带上自己的银行账号。
(2)顾客决定取消付款。顾客通知银行,把购物这笔钱保留在自己的银行账号上。
(3)商店送货给顾客。
(4)商店兑换货款。商店要求银行把顾客购物这笔钱划拨到自己的银行账号上。
(5)银行将这笔钱转账。银行把顾客购物这笔钱划拨给商店的账号。
……