第三章 有限自动机的基本概念.pdf

第三章 有穷状态自动机 软件开发环境国家重点实验室 第三章 有穷状态自动机 习题：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 的变形 - 带输出的 FA 3 一、有穷状态自动机定义与表示 识别正则语言的有穷自动机（FA ）模型实例： 例：L （G ）= { an n c | n ≧1 } ∪{ a d | n ≧1 } 。 有穷状态自动机定义与表示 识别语言自动机系统的结构及功能特征分析： 1、字母表：系统处理的所有字符串由字母表上的字符组成； 2、控制器：系统每次从输入字符串读入一个字符，并根据当前状态 和读入的字符，转入新的状态；新的状态和当前状态可以相同也可不 同；为此，系统具有有穷个状态,并需要维护一个读指针。 3、几个特殊状态： 一个开始状态；系统从此开始处理句子； 一些称之为终止状态或接受状态，系统从开始状态至此状态为 止，读入字符构成的字符串是语言的一个句子；系统到达这些 状态读入的全部字符串构成系统所能识别的语言。 有穷状态自动机定义与表示 有穷状态自动机装置的物理模型： 有穷状态自动机定义与表示 有穷状态自动机装置的组成： 1、一个具有一系列方格的输入字符串的带子：方格中存放字 符，字符从输入带左端开始存放，输入带右端无穷； 2、一个有穷状态控制器 FSC ：控制一个读头；每读入一个字 符，读头右移一格，指向下一个待读入字符。 有穷状态控制器 FSC 的基本工作过程： 控制器执行动作由三个节拍组成：⑴读头读入当前指向的字 符；⑵ 根据读入的字符和其自身当前状态，改变有穷状态控制 器的状态；⑶读头右移一格指向下一个字符。 有穷状态自动机定义与表示 定义3.1 ： 自动机的数学模型 一个 FA 为五元组 M = Q，∑，δ， q0 ，F 。其中， Q：非空有限的状态集合。 ∑：非空有限输入字符表。 δ：Q ×∑→Q 的状态转移函数：对 ∀q ∈Q 和 ∀a ∈∑, δ(q, a) = p 表示在状态 q 下读入字符 a， M 将状态变成 p，读头向右移动一个方格，指向输入字符串的下一个字 符。 q0： M 的开始状态， q0 ∈Q 。 F ：M 的终止状态，或接受状态。 8 有穷状态自动机定义与表示 设有限自动机 M = Q, ∑, δ, q , { q } , 其中，Q={ q , q , q , q } ； 0 2 0 1 2 3 ∑={ 0, 1, 2 } ；δ: Q ×∑→Q： 函数表示法： 状态图表示法： δ(q , 0)=q δ(q , 1) = q δ(q , 2) = q 0 1 0 3 0 3