形式语言与自动机

出版时间：2008-8  出版社：机械工业出版社  作者：陈有祺  页数：227  
Tag标签：无  

内容概要

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

作者简介

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

书籍目录

出版者的话序言前言教学建议第1章　预备知识　1.1　定理及其证明方法　　1.1.1　演绎法　　1.1.2　反证法　　1.1.3　归纳法　1.2　集合及其基本运算　　1.2.1　集合基础知识　　1.2.2　集合的基本运算　　1.2.3　关系与映射　1.3　图和树简介　　1.3.1  图的基本概念　　1.3.2  图的矩阵表示　　1.3.3　树的基本知识　1.4　字母表、字符串和语言　习题第2章　文法的一般理论　2.1　问题的提出　2.2　形式文法与形式语言　2.3　文法的乔姆斯基分类　习题第3章　有穷自动机　3.1　非形式化描述　3.2　有穷自动机的基本定义　3.3　非确定的有穷自动机　3.4　具有￡转移的有穷自动机　3.5　有穷自动机的应用　　3.5.1　在文本中查找字符串　　3.5.2　用于文本搜索的非确定的有穷自动机　　3.5.3　识别关键字集合的DFA  3.6　具有输出的有穷自动机  习题第4章　正则表达式  4.1　正则表达式的定义  4.2　正则表达式和有穷自动机的关系  4.3  则表达式的等价变换　　4.3.1　交换律与结合律　　4.3.2　单位元与零元　　4.3.3　分配律　　4.3.4　与“*”构造有关的定律　　4.3.5　发现正则表达式定律的一般方法  4.4　正则表达式的应用　　4.4.1  UNIX中的正则表达式　　4.4.2　词法分析　　4.4.3　查找文本中的模式  习题第5章  正则语言的性质  5.1　正则文法和有穷自动机的关系  5.2　正则语言的泵引理  5.3　正则语言的封闭性  5.4　正则语言的判定算法  5.5　有穷自动机的最小化  习题第6章　上下文无关文法  6.1  上下文无关文法的语法分析  6.2　上下文无关文法的化简  6.3　上下文无关文法的范式  6.4　上下文无关文法的应用　　6.4.1　用上下文无关文法描述语言　　6.4.2　语法分析器生成工具YACC　　……第7章　下推自动机第8章　上下文无关语言的性质　第9章　图灵机导引第10章　不可判定性第11章　线性有界自动机和上下文有关文法第12章　确定的上下文无关语言和LR（k）文法参考文献

章节摘录

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

用户评论 (总计8条)

•   非常适合计算原理学习
•   很多地方用不到答案也难找
•   除了书被折得有点厉害外，其他还行
•   还行 没想象的好
•   纸质不是特别的好，但书中错误很少，是正品；配送速度挺快
•   很好，书讲得很好，质量也很好。
•   因为老师讲的是这本书。学校也没有配发。。所以就来这买了本。。用着还可以。。
•   书还没用过，不过质量不错。。