形式语言与自动机理论电子教案-03.pptVIP

第3章 有穷状态自动机 主要内容 确定的有穷状态自动机(DFA) 作为对实际问题的抽象、直观物理模型、形式定义，DFA接受的句子、语言，状态转移图。 不确定的有穷状态自动机(NFA) 定义； NFA与DFA的等价性； 第3章 有穷状态自动机 带空移动的有穷状态自动机(ε-NFA) 定义。 ε-NFA与DFA的等价性。 FA是正则语言的识别器 正则文法(RG)与FA的等价性。 相互转换方法。 带输出的有穷状态自动机。 双向有穷状态自动机。 第3章 有穷状态自动机 重点：DFA的概念，DFA、NFA、ε-NFA 、RG之间的等价转换思路与方法。 难点：对DFA概念的理解，DFA、RG的构造方法， RG与FA的等价性证明。 3.1 语言的识别 推导和归约中的回溯问题将对系统的效率产生极大的影响 S?aA|aB A?aA|c B?aB|d 分析句子aaac 的过程中可能需要回溯。 3.1 语言的识别 系统识别语言{anc|n≥1}∪{and|n≥1}的字符串过程中状态的变化图示如下： 3.1 语言的识别 识别系统(模型) ⑴ 系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。 ⑵ 我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。 3.1 语言的识别 ⑶ 系统在任何一个状态(当前状态)下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态，也可以是不同的状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一个字符后指向输入串的下一个字符。 3.1 语言的识别 ⑷ 系统中有一个状态，它是系统的开始状态，系统在这个状态下开始进行某个给定句子的处理。 ⑸ 系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。 3.1 语言的识别 相应的物理模型 一个右端无穷的输入带。 一个有穷状态控制器(finite state control,FSC) 。 一个读头。 系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入的字符改变有穷控制器的状态；将读头向右移动一格。 3.1 语言的识别 有穷状态自动机的物理模型 3.2有穷状态自动机 有穷状态自动机(finite automaton,FA) M=(Q，∑，δ，q0，F) Q——状态的非空有穷集合。?q∈Q，q称为M的一个状态(state)。 ∑——输入字母表(Input alphabet)。输入字符串都是∑上的字符串。 q0——q0∈Q，是M的开始状态(initial state)，也可叫做初始状态或者启动状态。 3.2有穷状态自动机 δ——状态转移函数(transition function)，有时候又叫做状态转换函数或者移动函数。δ：Q×∑?Q，对?(q，a)∈Q×∑，δ(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串的下一个字符。 F——F?Q，是M的终止状态(final state)集合。?q∈F，q称为M的终止状态，又称为接受状态(accept state)。 3.2有穷状态自动机 例 3-1 下面是一个有穷状态自动机 M1=({q0，q1，q2}，{0}，δ1，q0，{q2}) 其中，δ1(q0,0)= q1，δ1(q1,0)= q2，δ1(q2,0)= q1 用表3-1表示δ1。 3.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)= q3 3.2有穷状态自动机 3.2有穷状态自动机 将δ扩充为 3.2有穷状态自动机 3.2有穷状态自动机 确定的有穷状态自动机 由于对于任意的q∈Q， a∈∑，δ(q，a)均有确定的值，所以，将这种FA称为确定的有穷状态自动机(deterministic finite automaton，DFA) 3.2有穷状态自动机 M接受(识别)的语言 对于?x∈∑*如果δ(q，w)∈F，则称x被M接受，如果δ(q