形式语言与自动机理论pdf

‘壹’ 形式语言与自动机^计算机数学

所谓形式，就是和实物、实际、具体相对而言，是抽象的，纯粹理论的。形而上学的“形”，也是这个意思。
基本上，形式语言是以数学描述语言。比如语句最终由“终结符号”组成，这里主要就是集合论的内容；“产生式”，又相当于映射或者函数。
程序设计语言是形式语言，但形式语言的涵义要深、广。

自动机理论主要是对“通用计算”的抽象。有了对通用计算的描述，使用机械让计算自动起来就只是一个工程技术上的问题。

基本上说，这些理论背后的数学是离散数学。

‘贰’ 泵引理（形式语言与自动机理论）正规语言

形式语言 形式语言是一个字母表上的某些有限长字串的集合。一个形式语言可以包含无限多个字串。 语言的形式定义 字母表∑为任意有限集合,ε表示空串,记∑0为{ε},全体长度为n的字串为∑n,∑*为∑0∪∑1∪…∪∑n...

‘叁’ 有限自动机理论的目录

第一章基础知识
1.1集合及其运算
1.2关系
1.2.1二元关系
1.2.2等价关系
1.2.3关系的合成
1.3证明和证明的方法
1.3.1反证法
1.3.2归纳法
1.3.3递归的定义与归纳证明
1.4图与树
1.5语言
1.6常用术语
1.7形式语言与自动机的发展
习题一
第二章形式语言
2.1例子语言
2.2文法和语言的关系
2.3Chomsky对文法的分类
2.4文法产生语言
2.5推导树
2.6空串定理
2.7消除左递归
2.7.1消除直接左递归
2.7.2消除间接左递归
2.8上下文无关文法的另一种表示
2.9语言之间的运算及运算的封闭性
2.9.1语言之间的基本运算
2.9.2语言之间的运算的封闭性
2.9.3语言之间的其他运算
2.10正则表达式和正则集
习题二
第三章有限状态自动机
3.1有限状态自动机
3.2有限状态自动机识别的语言
3.3有限状态自动机识别语言的例子
3.4不确定的有限状态自动机
3.4.1不确定的有限状态自动机
3.4.2不确定的有限状态自动机的确定化
3.5带有s动作的有限状态自动机
3.6有限状态自动机的一些变形
3.6.1双向的有限状态自动机
3.6.2带有输出的有限状态自动机
3.7有限状态接收机的存储技术
习题三
第四章正则语言
4.1正则语言与有限状态自动机
4.1.1正则表达式对应有限状态自动机
4.1.2正则语言的等价模型
4.2正则语言的泵浦引理
4.3正则语言对运算的封闭性
4.4正则语言类中的判定算法
习题四
第五章下推自动机
5.1下推自动机
5.1.1确定的下推自动机
5.1.2不确定的下推自动机
5.1.3下推自动机接收语言的两种方式
5.1.4广义的下推自动机和单态下推自动机
5.1.5下推自动机的存储技术
5.1.6下推自动机扫描多个符号
5.2上下文无关文法和范式
5.2.1Chomsky范式
5.2.2Greibach范式
5.3下推自动机与上下文无关语言
习题五
第六章图灵机
参考文献

‘肆’ 请问什么是形式语言与自动机

形式语言
形式语言 是一个字母表上的某些有限长字串的集合。一个形式语言可以包含无限多个字串。

语言的形式定义
字母表 ∑ 为任意有限集合，ε 表示空串， 记 ∑ 0 为{ε}，全体长度为 n 的字串为 ∑ n ， ∑ * 为 ∑ 0 ∪∑ 1 ∪…∪∑ n ∪…， 语言 L 定义为 ∑ * 的任意子集。

注记：∑ * 的空子集 Φ 与 {ε} 是两个不同的语言。

语言间的运算
语言间的运算就是 ∑ * 幂集上的运算。

字串集合的交并补等运算。
连接运算：L 1 L 2 = { xy | x 属于L 1 并且 y 属于L 2 }。
幂运算：L n = L … L （共 n 个 L 连接在一起），L 0 = {ε}。
闭包运算：L * = L 0 ∪L 1 ∪…∪L n ∪…。
（右）商运算：L 1 /L 2 = {x | 存在 y 属于L 2 使得 xy 属于L 1 }。
语言的表示方法
一个形式语言可以通过多种方法来限定自身，比如：

枚举出各个字串（只适用于有限字串集合）。
通过 形式文法 来产生（参见 乔姆斯基谱系 ）。
通过正则表达式来产生。
通过某种自动机来识别，比如 图灵机 、 有限状态自动机 。
自动机
automata

对信号序列进行逻辑处理的装置。在自动控制领域内，是指离散数字系统的动态数学模型，可定义为一种逻辑结构，一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中，分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论。在语言学中则把自动机作为语言识别器，用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型，用来研究神经生理活动和思维规律，探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型，研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数，研究各种算法。现代自动机的一个重要特点是能与外界交换信息，并根据交换得来的信息改变自己的动作，即改变自己的功能，甚至改变自己的结构，以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。
自动机与一般机器的重要区别在于自动机具有固定的内在状态，即具有记忆能力和识别判断能力或决策能力，这正是现代信息处理系统的共同特点。因此，自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。自动机可按其变量集和函数的特性分类，也可按其抽象结构和联结方式分类。主要有：有限自动机和无限自动机、线性自动机和非线性自动机、确定型自动机和不确定型自动机、同步自动机和异步自动机、级联自动机和细胞自动机等。

‘伍’ 计算机科学与技术（专业限选课）~~

我也是计算机科学与技术专业的，也读大二，冒昧说下自己的看法，呵呵。。
Java语言程序设计：Java是目前最流行的两个开发环境之一（另一个是微软的.NET），现在很多软件，尤其是手机软件都是由Java写的，如果你将来从事软件开发的话这会是很重要的一门技能。
形式语言与自动机理论是关于理论计算机的，理论研究用的。个人觉得你将来如果不专门做计算机方面的研究工作这个是不会用到太多的。
计算机图形学是非常重要的一门学科，是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。其实就是研究计算机如何处理和表现图形的。
单片机原理和接口技术、嵌入式系统都是硬件方面的。前者主要是讲单片机的原理制作以及计算机的各种接口，像网卡接口、声卡接口这些。嵌入式系统就是在某种器件上面集成各种芯片什么的来完成不同功能。
我也刚入门，懂得不多，见谅啦~~~

‘陆’ 形式语言与自动机理论（第2版）清华大学出版社的课后答案

第1章 概 述
习题(答案)
一．选择题
1. D 2. B 3. CD 4. C 5. ABC
6. A 7. B 8. B 9. ABCD 10. ABCDE

二．简答题
1．什么是计算机系统？
计算机系统是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和存储的系统，由计算机硬件系统和计算机软件系统两大部分组成。
2．请解释冯•诺依曼所提出的“存储程序”概念。
把程序和数据都以二进制的形式统一存放在存储器中，由机器自动执行。不同的程序解决不同的问题，实现了计算机通用计算的功能。
3．控制器的主要功能是什么？
控制器基本功能就是从内存中取出指令和执行指令，即控制器按程序计数器指出的指令地址从内存中取出该指令进行译码，然后根据该指令功能向有关部件发出控制命令，执行该指令。另外，控制器在工作过程中，还要接受各部件反馈回来的信息。
4．简述CPU和主机的概念。
通常把运算器、控制器做在一个大规模集成电路块上称为中央处理器，又称CPU(Central Processing Unit)。
通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由CPU与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入/输出设备，外存储器等。
5．什么是计算机软件？计算机软件的分类有哪些？
软件是指用来指挥计算机运行的各种程序的总和以及开发、使用和维护这些程序所需的技术文档。
计算机软件系统分为系统软件和应用软件。计算机系统软件由操作系统、语言处理系统、以及各种软件工具等组成，指挥、控制计算机硬件系统按照预定的程序运行、工作，从而达到预定的目标。应用软件是用户利用计算机软、硬件资源为解决各类应用问题而编写的软件，包括用户程序及其说明性文件资料。
6．计算机有哪些主要的特点？
(1)运算速度快、精度高
计算机的字长越长，其精度越高，现在世界上最快的计算机每秒可以运算几十万亿次以上。一般计算机可以有十几位甚至几十位(二进制)有效数字，计算精度可由千分之几到百万分之几，是任何计算工具所望尘莫及的。
(2)具有逻辑判断和记忆能力
计算机有准确的逻辑判断能力和高超的记忆能力。能够进行各种逻辑判断，并根据判断的结果自动决定下一步应该执行的指令。
(3)高度的自动化和灵活性
计算机采取存储程序方式工作，即把编好的程序输入计算机，机器便可依次逐条执行，这就使计算机实现了高度的自动化和灵活性。
7．计算机的分类有哪些？
根据计算机工作原理和运算方式的不同，以及计算机中信息表示形式和处理方式的不同，计算机可分为数字式电子计算机(Digital Computer)、模拟式电子计算机(Analog Computer)和数字模拟混合计算机(Hybrid Computer)。当今广泛应用的是数字计算机，因此，常把数字式电子计算机(Electronic Digital Computer)简称为电子计算机或计算机。
按计算机的用途可分为通用计算机(General Purpose Computer)和专用计算机(Special Purpose Computer )两大类。通用计算机能解决多种类型问题，是具有较强通用性的计算机，一般的数字式电子计算机多属此类；专用计算机是为解决某些特定问题而专门设计的计算机，如嵌入式系统。
根据计算机的总体规模对计算机分类，可分为巨型机(Super Computer)、大/中型计算机(Mainframe)、小型计算机(Mini computer)、微型计算机(Micro computer)和网络计算机(Network Computer)五大类。
常见的微型机还可以分为台式机、便携机、笔记本电脑、掌上型电脑等多种类型。
8．简述计算机的基本运行方式。
计算机的基本运作方式可概括为所谓的“IPOS循环”。IPOS循环即输入(Input)、处理(Processing)、输出(Output)和存储(Storage)，它反映了计算机进行数据处理的基本步骤。
(1)输入
接受由输入设备(如键盘、鼠标器、扫描仪等)提供的数据。
(2)处理
对数值、逻辑、字符等各种类型的数据进行操作，按指定的方式进行转换。
(3)输出
将处理所产生的结果等数据由输出设备(如显示器、打印机、绘图仪等)进行输出。
(4)存储
计算机可以存储程序和数据供以后使用。
9．计算机有哪些主要的用途？
(1)科学计算
使用计算机来完成科学研究和工程技术中所遇到的数学问题的计算称为科学计算，也称为数值计算。科学计算是使用计算机完成在科学研究和工程技术领域中所提出的大量复杂的数值计算问题，是计算机的传统应用之一。
(2)信息处理
所谓信息处理就是使用计算机对数据进行输入、分类、加工、整理、合并、统计、制表、检索以及存储等，又称为数据处理。例如座席预订与售票系统、零售业中的应用、办公自动化等。信息处理已成为当代计算机的主要任务，是现代化管理的基础。
(3)实时控制(也称过程控制)
实时控制也称过程控制，实时控制能及时地采集检测数据、使用计算机快速地进行处理并自动地控制被控对象的动作，实现生产过程的自动化。
(4)计算机辅助设计/辅助制造/辅助教学
计算机辅助设计(Computer Aided Design——CAD)是使用计算机来辅助人们完成产品或工程的设计任务的一种方法和技术。计算机辅助制造(Computer Aided Manufacturing——CAM)是使用计算机辅助人们完成工业产品的制造任务，能通过直接或间接地与工厂生产资源接口的计算机来完成制造系统的计划、操作工序控制和管理工作的计算机应用系统。计算机辅助教学(Computer Aided Instruction——CAI)是把计算机用作教学媒体，使它充当指导者、工具和学习者角色，学生通过与计算机的对话进行学习的一种新型教学技术。
(5)人工智能
人工智能(Artificial Intelligence——AI)就是指计算机模拟人类某些智力行为的理论、技术和应用。
(6)多媒体技术
随着电子技术特别是通信和计算机技术的发展，人们已经有能力把文本、音频、视频、动画、图形和图像等各种媒体综合起来，构成“多媒体”(Multimedia)的概念。
10．简述计算机的发展趋势。
(1)微型化
一方面，随着计算机的应用日益广泛，在一些特定场合，需要很小的计算机，计算机的重量、体积都变得越来越小，但功能并不减少。另一方面，随着计算机在世界上日益普及，个人电脑正逐步由办公设备变为电子消费品。人们要求电脑除了要保留原有的性能之外，还要有时尚的外观、轻便小巧、便于操作等特点，如平板电脑、手持电脑等。今后个人计算机(Personal Computer)在计算机中所占的比重将会越来越大，使用也将会越来越方便。
(2)巨型化
社会在不断发展，人类对自然世界的认识活动也越来越多，很多情况要求计算机对数据进行运算。“巨型化”在这里并不是通常意义上的大小，主要是指机器的性能——运算速度等。
(3)网络化
因特网(Internet)的建立正在改变我们的世界，改变我们的生活。网络具有虚拟和真实两种特性，网上聊天和网络游戏等具有虚拟特性，而网络通信、电子商务、网络资源共享则具有真实的特性。
(4)智能化
今后，计算机在生活中扮演的角色将会更加重要,计算机应用将具有更多的智能特性，能够帮助用户解决—些自己不熟悉或不愿意做的事，如智能家电、烹调等。
(5)新型计算机
目前新一代计算机正处在设想和研制阶段。新一代计算机是把信息采集、存储处理、通信和人工智能结合在一起的计算机系统。
11．简述计算学科的定义、计算学科的本质、计算学科的三个过程。
计算学科是对描述和变换信息的算法过程，包括对理论分析、设计、效率、实现和应用等进行的系统研究。计算学科的研究包括了从算法与可计算性的研究到根据可计算硬件和软件的实际实现问题的研究。
计算学科的根本问题是“什么能被有效地自动进行？”。计算学科的根本问题讨论的是能行性的有关内容，而凡是与能行性有关的讨论都是处理离散对象的。
计算学科的实质是学科方法论的思想，其关键问题是抽象、理论和设计三个过程相互作用的问题。
(1)理论
理论是数学科学的根本。应用数学家们都认为，科学的进展都是基于纯数学的。应用数学用数学的方法推动经验科学和工程学的发展，同时又不断刺激对新数学的需要，为纯理论数学提出新的问题。
(2)抽象
抽象(模型化)是自然科学的根本。科学家们相信，科学进展的过程基本上都是形成假设，然后用模型化过程去求证。
(3)设计
设计是工程的根本。工程师们认为，工程进展基本上都是提出问题，然后通过设计去构造系统，以解决问题。
12．简述计算机科学与技术学科的定义。
计算机科学技术是研究计算机的设计与制造和利用计算机进行信息获取、表示、存储、处理、控制等的理论、原则、方法和技术的学科，包括科学与技术两方面。科学侧重于研究现象、揭示规律；技术则侧重于研制计算机和研究使用计算机进行信息处理的方法与技术手段。科学是技术的依据，技术是科学的体现；技术得益于科学，它又向科学提出新的课题。
13．简述计算机科学课程体系的核心内容。
计算学科课程体系的教学内容归结为14个知识体，包括：
(1)离散结构(PS)
计算学科是以离散型变量为研究对象，离散数学对计算技术的发展起着十分重要的作用。随着计算技术的迅猛发展，离散数学越来越受到重视。
(2)程序设计基础(PF)
《计算作为一门学科》报告指出了程序设计在计算学科的正确地位：程序设计是计算学科课程中固定练习的一部分，是每一个计算学科专业的学生应具备的能力，是计算学科核心科目的一部分，程序设计语言还是获得计算机重要特性的有力工具。
(3)算法与复杂性(AL)
算法是计算机科学和软件工程的基础，现实世界中，任何软件系统的性能仅依赖于两个基本点方面，一方面是所选择的算法；另一方面是各不同层次实现的适宜性和效率。
(4)组织与体系结构(AR)
计算机在计算中处于核心地位，如果没有计算机，计算学科只是理论数学的一个分支，应该对计算机系统的功能构件、以及他们的特点/性能和相互作用有一定的理解。
(5)操作系统(OS)
操作系统定义了对硬件行为的抽象，程序员用它来对硬件进行控制。操作系统还管理计算机用户间的资源共享。
(6)网络计算(NC)
计算机和通信网络的发展，尤其是基于TCP/IP的网络的发展使得网络技术在计算学科中更加重要。
(7)程序设计语言(PL)
程序设计语言是程序员与计算机交流的主要工具。一个程序员不仅要知道如何使用一种语言进行程序设计，还应理解不同语言的程序设计风格。
(8)人-机交互(HL)
人机交互重点在于理解人对交互式对象的交互行为，知道如何使用以人为中心的方法开发和评价交互软件系统，以及人机交互设计问题的一般知识。
(9)图形学和可视化计算(GV)
该主领域的主要内容包括：计算机图形学、可视化、虚拟现实、计算机视觉等4 个学科子领域的研究内容。
(10)智能系统(IS)
人工智能领域关心的问题是自主代理的设计和分析。智能系统必须干知其环境，合理地朝着指定的任务行动，并与其它代理和人进行交互。
(11)信息管理(IM)
信息系统几乎在所有使用计算机的场合都发挥着重要的作用。
(12)软件工程(SE)
软件工程是关于如何有效地利用建立满足用户和客户需求的软件系统理论/知识和实践的学科，可以应用于小型、中型、大型系统。
(13)数值计算科学(CN)
从计算学科的诞生之日起，科学计算的数值方法和技术就构成了计算机科学研究的一个主要领域。
(14)社会和职业问题(SP)
大学生需要懂得计算学科本身基本的文化、社会、法律和道德问题。还需要培养学生提出有关计算的社会影响这样严肃问题以及对这些问题的可能答案进行评价的能力。学生还需要认识到软硬件销售商和用户的基本法律权利，也应意识到这些权利的基本基础——道德价值观。

三．讨论题
1．计算机的产生是世纪最伟大的成就之一，具体体现在哪些方面？根据你的观察，请列出计算机的应用。
答案略。
2．计算机提供了无限的机会和挑战。利用它可以更快更好地完成许多事情，可以方便地和全世界的人们联系和通信。但是，是否想过事情的反面呢？所有的变化都是积极的么？计算机的广泛使用会产生什么负面的影响吗？讨论这些问题和其他所能想到的问题。
答案略。

是这个吗?

‘柒’ 《编译原理》pdf下载在线阅读，求百度网盘云资源

《编译原理》（陈意云）电子书网盘下载免费在线阅读

链接：

书名：编译原理

作者：陈意云

豆瓣评分：6.2

出版社：高等教育出版社

出版年份：2003-1

页数：381

内容简介：

《编译原理》介绍编译器构造的一般原理和基本实现方法，主要内容包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等。除了介绍命令式编程语言的编译技术外，《编译原理》还介绍面向对象语言和函数式编程语言的实现技术。《编译原理》还强调一些相关的理论知识，如形式语言和自动机理论、语法制导的定义和属性文法、类型论和类型系统等。

《编译原理》取材广泛新颖、图文并茂，注意理论联系实际。为满足教师教学和学生自学及考研需求，《编译原理》作者编写了配套教学参考书《编译原理习题精选与解析》（高等教育出版社2005年8月出版），同时提供本课程的电子教案，可从高等教育出版社高等理工教学资源网免费下载。《编译原理》可作为高等学校计算机科学及相关专业的教材，也可供计算机软件工程技术人员参考使用。

‘捌’ 形式语言与自动机理论

《形式语言与自动机》是关于理论计算机的，理论研究用的。从事计算机科学没有理论知识是不行的。
《模糊数学》跟纯数据库没有什么直接关系，但是以后你做数据仓库与知识挖掘的话会用到人工智能和模糊数学的
感觉《随即过程》和人工智能和网络的关系比较大。《计算机体系结构》是计算机科学与技术专业必须要学的，以后凡是涉及到硬件结构与组织形式的课程都会用到它
顺便问一句你很喜欢数据库吗？无论你以后做计算机的哪方面工作，都要对计算机有一个相对全面的了解，打好基础，不要急功近利。一点小小建议