有限自动机理论03章有限状态自动机.ppt

《有限自动机理论03章有限状态自动机.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、PDA图灵机TM有限状态自动机FA(FinitestateAutomaton)FA是为研究有限存储的机制和正则语言而抽象出的一种模型。两类有限状态自动机接收器判断是否接收输入串；转换器对给定输入串产生输出。FA还可以分为确定的FA----DFADeterministicFinitestateAutomaton非确定FA----NFANon-deterministicFinitestateAutomaton等价性有限状态自动机接收的语言称为有限状态语言--FSL从产生语言角度而言，FSL就是右线性语言--RLL从(正则)运算角度而言

3、，FSL就是正则语言--RL有限状态自动机除在理论上的研究价值外还在数字电路设计、编译技术(词法分析)、系统辅助软件(文本编辑程序)、漏洞检测、交通控制等应用领域得到广泛应用3.1有限状态自动机有限状态自动机是具有离散输入和离散输出的一种数学模型。有限状态自动机是否接收串w有限状态自动机是否接收语言L有限状态自动机物理模型a1a2a3…aj…anan+1…FSC一个输入存储带（输入带），带被分解为单元，每个单元存放一个输入符号(字母表上的符号)。整个输入串从带的左端点开始存放，而带的右端可以无限扩充；一个有穷状态控制器（FSC）该控

4、制器的状态只能是有限多个FSC通过读头读取当前带上单元的字符。初始时，读头对应带的最左单元，每读取一个字符，读头向右自动移动一个单元。读头（暂时）不允许向左移动。有限状态自动机的一个动作为：读头读取带上当前单元的字符FSC根据当前FSC的状态和读取的字符，进行状态改变；将读头向右移动一个单元。有限态自动机的动作可以简化为：FSC根据当前状态和当前读取的带上字符进行状态改变。定义3-1有限状态自动机FAFA是一个五元式FA=(Q，∑，δ，q0，F)Q是有限状态的集合∑是字母表，即输入带上的字符集合q0∈Q是开始状态FQ是接收状态(终

5、止状态)集合δ是Q×∑→Q的状态转换函数即δ(q，x)=q′代表FA在状态q时，扫描字符x后状态改变为q′（也称到达状态q′）有限状态自动机的状态转换函数的个数应该为

6、Q

7、*

8、∑

9、对于Q中的每个状态，需要定义对应∑每个字母的状态转换。DFA这种有限状态自动机为确定的有限状态自动机DFA。例3-1定义DFA为：DFA=({q0,q1},{0,1},δ,q0,{q0})其中δ：δ的表示：函数形式δ(q0，0)=q1δ(q0，1)=q1δ(q1，0)=q1δ(q1，1)=q0δ的表示：状态矩阵Q∑0q01q1q1q1q1q0δ的表示:状态

10、图形式状态图是一个有向、有循环的图一个节点表示一个状态；若有δ(q，x)=q′，则状态q到状态q′有一条有向边，并用字母x作标记。δ的表示‘→’指向的状态是开始状态两个圆圈代表接收状态；δ的表示：状态图q11010q0用状态图表示一个DFA有向边的数目就是状态转换函数的个数。默认有δ(q,ε)=q但不是状态转换函数why?3.2有限状态自动机接收语言对于DFA，给定串w=x1x2…xn初始时，DFA处于开始状态q0从左到右逐个字符地扫描串w在δ(q0，x1)=q1的作用下DFA处于状态q1在δ(q1，x2)=q2的的作用下DFA处于

11、状态q2…当将串w扫描结束后，若DFA处于某一个接收状态，则有限状态自动机能够接收串w对于可接收串DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，处于某个接收状态。对于不可接收串DFA从开始状态开始，在扫描串的过程中，状态逐个地变化,串扫描结束后，处于某个非接收状态。对于字母表∑上的DFA能够接收的所有串的集合，就是DFA能接收的语言，记为L(DFA)也称为有限状态语言（FSL）思考如何形式化定义L(DFA)?定义3-4扩展的状态转换函数给定DFA，扩展的状态转换函数δ*：Q×∑*→Q即δ*(q,w)=q′即D

12、FA在一个状态q时，扫描串w后到达唯一确定的状态q′递归扩展的状态转换函数δ*(q,ε)=qδ*(q,a)=δ(q,a)其中a∈∑对于串w=αa（α∈∑+）δ*（q，w）=δ*(q，αa）=δ(δ*(q,α),a)或者对于串w=aαδ