形式语言第3章有穷状态自动机

《形式语言第3章有穷状态自动机》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/7/191第3章有穷状态自动机主要内容确定的有穷状态自动机(DFA)作为对实际问题的抽象、直观物理模型、形式定义，DFA接受的句子、语言，状态转移图。不确定的有穷状态自动机(NFA)定义；NFA与DFA的等价性；2021/7/192第3章有穷状态自动机带空移动的有穷状态自动机(ε-NFA)定义。ε-NFA与DFA的等价性。FA是正则语言的识别器正则文法(RG)与FA的等价性。相互转换方法。带输出的有穷状态自动机。双向有穷状态自动机。2021/7/193第3章有穷状态自动机重点：DFA的概念，DFA、NFA、

2、ε-NFA、RG之间的等价转换思路与方法。难点：对DFA概念的理解，DFA、RG的构造方法，RG与FA的等价性证明。2021/7/1943.1语言的识别推导和归约中的回溯问题将对系统的效率产生极大的影响SaA

3、aBAaA

4、cBaB

5、d分析句子aaac的过程中可能需要回溯。2021/7/1953.1语言的识别系统识别语言{anc

6、n≥1}∪{and

7、n≥1}的字符串过程中状态的变化图示如下：2021/7/1963.1语言的识别识别系统(模型)⑴系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以

8、在不同的状态下完成规定的任务。⑵我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。2021/7/1973.1语言的识别⑶系统在任何一个状态(当前状态)下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态，也可以是不同的状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一个字符后指向输入串的下一个字符。2021/7/1983.1语

9、言的识别⑷系统中有一个状态，它是系统的开始状态，系统在这个状态下开始进行某个给定句子的处理。⑸系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。2021/7/1993.1语言的识别相应的物理模型一个右端无穷的输入带。一个有穷状态控制器(finitestatecontrol,FSC)。一个读头。系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入的字符改变有穷控制器的状态；将读头

10、向右移动一格。2021/7/19103.1语言的识别有穷状态自动机的物理模型2021/7/19113.2有穷状态自动机有穷状态自动机(finiteautomaton,FA)M=(Q，∑，δ，q0，F)Q——状态的非空有穷集合。q∈Q，q称为M的一个状态(state)。∑——输入字母表(Inputalphabet)。输入字符串都是∑上的字符串。q0——q0∈Q，是M的开始状态(initialstate)，也可叫做初始状态或者启动状态。2021/7/19123.2有穷状态自动机δ——状态转移函数(transitionf

11、unction)，有时候又叫做状态转换函数或者移动函数。δ：Q×∑Q，对(q，a)∈Q×∑，δ(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串的下一个字符。F——FQ，是M的终止状态(finalstate)集合。q∈F，q称为M的终止状态，又称为接受状态(acceptstate)。2021/7/19133.2有穷状态自动机例3-1下面是一个有穷状态自动机M1=({q0，q1，q2}，{0}，δ1，q0，{q2})其中，δ1(q0,0)=q1，δ1(q1,0)=

12、q2，δ1(q2,0)=q1用表3-1表示δ1。状态说明状态输入字符0开始状态q0q1q1q2终止状态q2q12021/7/19143.2有穷状态自动机M2=({q0，q1，q2，q3}，{0，1，2}，δ2，q0，{q2})δ2(q0,0)=q1，δ2(q1,0)=q2δ2(q2,0)=q1，δ2(q3,0)=q3δ2(q0,1)=q3，δ2(q1,1)=q3δ2(q2,1)=q3，δ2(q3,1)=q3δ2(q0,2)=q3，δ2(q1,2)=q3δ2(q2,2)=q3，δ2(q3,2)=q32021/7/191

13、53.2有穷状态自动机状态说明状态输入字符012开始状态q0q1q3q3q1q2q3q3终止状态q2q1q3q3q3q3q3q3表3-2δ2转换函数2021/7/19163.2有穷状态自动机将δ扩充为对任意的q∈Q，w∈∑*，a∈∑，定义2021/7/19173.2有穷状态自动机两值相同，不用区分这两个符号。2021/7/19183.2有穷状态