下载文档原格式
第三章有穷状态自动机软件开发环境国家重点实验室第三章有穷状态自动机习题：P126题1；题2 -1、2、3、4、5、6、9、10；题5；题7；题10 -1、2、3、4、5、6；题11；题14；题15；题20；题21思考题：题19、题24。
第三章有穷状态自动机一、有穷状态自动机FA 定义与表示二、确定的有穷自动机DFA三、非确定的有穷自动机NFA四、DFA 和NFA 的等价性五、带空移动的有穷自动机ε-NFA六、FA 是正则语言的识别器–FA 与RG 关系七、FA 的变形-带输出的FA3识别正则语言的有穷自动机（FA ）模型实例：例：L （G ）= { a n c | n ≧1 } ∪{ a n d | n ≧1 }。
一、有穷状态自动机定义与表示有穷状态自动机定义与表示识别语言自动机系统的结构及功能特征分析：1、字母表：系统处理的所有字符串由字母表上的字符组成；2、控制器：系统每次从输入字符串读入一个字符，并根据当前状态和读入的字符，转入新的状态；新的状态和当前状态可以相同也可不同；为此，系统具有有穷个状态,并需要维护一个读指针。
3、几个特殊状态：9一个开始状态；系统从此开始处理句子；9一些称之为终止状态或接受状态，系统从开始状态至此状态为止，读入字符构成的字符串是语言的一个句子；系统到达这些状态读入的全部字符串构成系统所能识别的语言。
有穷状态自动机定义与表示有穷状态自动机装置的物理模型：有穷状态自动机定义与表示有穷状态自动机装置的组成：1、一个具有一系列方格的输入字符串的带子：方格中存放字符，字符从输入带左端开始存放，输入带右端无穷；2、一个有穷状态控制器FSC：控制一个读头；每读入一个字符，读头右移一格，指向下一个待读入字符。
有穷状态控制器FSC 的基本工作过程：控制器执行动作由三个节拍组成：⑴读头读入当前指向的字符；⑵根据读入的字符和其自身当前状态，改变有穷状态控制器的状态；⑶读头右移一格指向下一个字符。
计算机组成原理与结构期末论文有限自动机的原理及示例学院：专业：姓名：学号：有限自动机的原理及示例本文将介绍几种重要有限自动机的基本原理，并通过例子说明它们的运行过程。
一． 语言的基本概念一张字母表是一个非空有限集合∑，字母表∑中的每个元素x 称为∑中的一个字母，也称符号、终止符或者字符。
∑中有限个字符1,,n a a 有序地排列起来12n x a a a =就称为∑上的一个字符串，n 称为它的长度。
其中有一个特殊的串ε，它的长度为零。
若1∑和2∑都是字母表，则它们的乘积12∑∑定义为{}12121122,a a a ∑∑=∈∑∈∑：a ，特别地， 0121{}n n ε-∑=∑=∑∑=∑∑∑=∑∑令*01kk k k ∞=∞+=∑=∑∑=∑若*,,x y z ∈∑，且z xy =则称,x y 是z 的子串。
字母表∑上的一种语言是*∑的一个子集L 。
二． 有限状态自动机的原理和运算实例1.基本原理一个有限状态自动机的物理模型通常包括两部分：（1）一个输入存储带，带被分解为多个单元，每个单元存放一个输入符号（字母表上的符号），整个输入串从带的左端点开始存放，而带的右端可以无限扩充。
（2）一个有限状态控制器（FSC ）,该控制器的状态只能是有限个；FSC 通过一个读头和带上单元发生耦合，可以读出当前带上单元的字符。
初始时，读头对应带的最左单元，每读出一个字符，读头向右移动一个单元。
有限状态自动机的一个动作为：读头读出带上当前单元的字符；FSC 根据当前FSC 的状态和读出的字符，改变FSC 的状态；并将读头右移一个单元。
接着给出有限状态自动机的数学模型。
字母表∑上的一个有限状态自动机(FSAM)是一个五元组()0,,,,,FSAM Q q F δ=∑ 其中，i)Q 是一个有限状态的集合；ii)∑是字母表，它是输入带上的字符的集合；iii)0q Q ∈是开始状态；iv)F Q ⊂是接收状态（终止状态）集合；v):Q Q δ⨯∑→是状态转换函数，(,)q x q δ'=表示自动机在状态q 时，扫描字符x 后到达状态q '。
