有限自动机理论.ppt

《有限自动机理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第三章有限状态自动机定义语言可以从两个方面进行：１）从产生语言的角度；２）从接收(或识别)语言的角度。形式语言研究内容产生一个语言:1)定义语言中的基本句子;2)根据其余句子的形成规则，产生出该语言所包含的所有句子。有限自动机研究内容使用某种自动机模型来接收字符串接收的所有字符串形成的集合，也是一个语言统一的理论形式语言与自动机作为统一的理论,实际上包括3个方面的内容:1)形式语言理论(产生语言)2)自动机理论(接收语言)3)形式语言与自动机的等价性理论有限状态自动机FA(FinitestateAutomaton)FA是为研

2、究有限存储的计算过程正则语言而抽象出的一种计算模型。两类有限状态自动机接收器判断是否接收输入串；转换器对给定输入产生输出。FA还可以分成确定（DFA）与非确定（NFA）两种。等价性有限状态自动机识别的语言称为有限状态语言--FSL.从产生语言角度而言，FSL就是右线性语言--RLL从正则运算角度而言，FSL就是正则语言--RL。有限状态自动机除了它在理论上的价值外，还在数字电路设计、词法分析、文本编辑程序等领域得到广泛应用3.1有限状态自动机有限状态自动机是具有离散输入和输出系统的一种数学模型。有限状态自动机物理模型a1a2a

3、3…aj…anan+1…FSC一个输入存储带（输入带），带被分解为单元，每个单元存放一个输入符号(字母表上的符号)。整个输入串从带的左端点开始存放，而带的右端可以无限扩充；一个有穷状态控制器（FSC）该控制器的状态只能是有限多个FSC通过一个读头读出当前带上单元的字符。初始时，读头对应带的最左单元，每读出一个字符，读头向右自动移动一个单元。读头(暂时)不允许向左移动。有限状态自动机的一个动作为：读头读出带上当前单元的字符FSC根据当前FSC的状态和读出的字符，进行状态改变；将读头向右移动一个单元。有限态自动机的动作简化为：FS

4、C根据当前状态和当前读取的带上字符进行状态改变。定义3-1有限状态自动机FAFA是一个五元式FA=(Q，∑，δ，q0，F)Q是有限状态的集合∑是字母表，也就是输入带上的字符的集合；q0∈Q是开始状态；FQ是接收状态(终止状态)集合；δ是Q×∑→Q的状态转换函数，即δ(q，x)=q′代表自动机在状态q时，扫描字符x后到达状态q′有限状态自动机的状态转换函数的个数应该为

5、Q

6、*

7、∑

8、对于Q中的每个状态，都应该定义对应∑的每个字母的状态转换。DFA这种有限状态自动机为确定的有限状态自动机DFA。例3-1DFA=({q0,q1},{

9、0,1},δ,q0,{q0})其中δ：δ的表示：函数形式δ(q0，0)=q1δ(q0，1)=q1δ(q1，0)=q1δ(q1，1)=q0δ的表示：状态矩阵Q∑0q01q1q1q1q1q0δ的表示:状态图形式状态图是一个有向、有循环的图一个节点表示一个状态；若有δ(q，x)=q′，则状态q到状态q′有一条有向边，并用字母x作标记。δ的表示‘→’指向的状态是开始状态两个圆圈代表接收状态；δ的表示：状态图q11010q0用状态图表示一个DFA有向边的数目就是状态转换函数的个数。3.2有限状态自动机识别语言对于DFA，给定串w=x1x

10、2…xn；初始时，DFA处于开始状态q0从左到右逐个字符地扫描串w在δ(q0，x1)=q1的作用下DFA处于状态q1在δ(q1，x2)=q2的的作用下DFA处于状态q2…当将串w扫描结束后，若DFA处于某一个接收状态，则有限状态自动机能够接收串w对于可接收串DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，到达某个接收状态。对于不可接收串DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，处于非接收状态。对于字母表∑上的DFA能识别的所有串的集合，就是DFA能接收的语言:L(DFA)也称为

11、有限状态语言（FSL）思考如何形式化定义L(DFA)?定义3-4扩展的状态转换函数给定DFA，扩展的状态转换函数δ*：Q×∑*→Q即δ*(q,w)=q′即DFA在一个状态q时，扫描串w后到达唯一确定的状态q′递归扩展的状态转换函数δ*(q,ε)=q；δ*(q,a)=δ(q,a)其中a∈∑；对于串w=αa（α∈∑+）δ*（q，w）=δ*(q，αa）=δ(δ*(q,α),a)或者对于串w=aαδ*(q，w)=δ*(q，aα)=δ*(δ(q，a),α)定义3-6DFA接收的语言DFA=(Q,∑,δ,q0，F)接收的语言L(DFA)=

12、{w

13、δ*(q0,w)∈F}思考如何描述在某个时刻，DFA所处的情况？定义3-7DFA的瞬时描述（格局）格局是一个二元式：qyq是DFA当前状态y是输入带上还没有被扫描到的串读头将扫描y串的第1个符号在扫描串的过程中，格局在发生转换(改变)格局的(一次)转换的原因是由于δ函数