形式语言与自动机

本书以四类形式语言（短语结构语言，上下文有关语言。上下文无关语言。正则语言）和四种自动机（有穷自动机、下推自动机．图灵机，线性有界自动机）为主线，讨论了形式语言与自动机方面的主要理论成果和应用实例。
　　本书的主要特色：
　　取材丰富。涵盖了该领域国内外现有教材的主要内容。
　　在写作方法上，循序渐进，深入浅出。在概念的引入和定理的证明上，尽量采用通俗的语言和形象化的方法来表达。
　　理论与实际相结合。除具有配合定理和定义的大量例题外，许多章节还有现代计算机技术中应用的实例。
　　适合作为研究生的教材。

本书以四类形式语言（短语结构语言、上下文有关语言、上下文无关语言、正则语言）和四种自动机（有穷自动机、下推自动机、图灵机、线性有界自动机）为主线，讨论了形式语言与自动机方面的主要理论成果和应用实例。书中每一章的最后都配有大量不同难度的习题，有助于读者掌握本书内容。
本书采用通俗的语言和形象化的方法来表达概念和定理，逻辑严谨、思维缜密，可作为高等院校计算机及相关专业硕士“形式语言与自动机”课程的教材。

陈有祺，南开大学信息技术科学学院教授，多年来一直从事计算机软件方面的教学和研究工作，从1993年起享受国务院政府特殊津贴。讲授的课程主要有程序设计语言．编译原理，数据结构、形式语言与自动机等，研究领域包括编译理论、人工智能、自然语言理解，形式语言等。1980年至1

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