形式语言与自动机-2015-第03讲-有穷自动机(1)

1、形式语言与自动机形式语言与自动机Formal Languages and Automata Theory教师：康建初、胡春明、教师：康建初、胡春明、赵永望赵永望http:/ 有穷自动机有穷自动机第三章第三章 有穷状态自动机有穷状态自动机一、有穷状态自动机一、有穷状态自动机 FA FA 定义与表示定义与表示二、确定的有穷自动机二、确定的有穷自动机 DFADFA三、非确定的有穷自动机三、非确定的有穷自动机 NFANFA四、四、DFA DFA 和和 NFA NFA 的等价性的等价性五、带空移动的有穷自动机五、带空移动的有穷自动机- NFA- NFA六、六、FA FA 是正则语言的识别器是正则语言的识

2、别器 七、七、FA FA 的变形的变形 - - 带输出的带输出的 FAFA第第一一次课次课第二第二次课次课语言的识别语言的识别方法方法1：根据：根据G的定义，寻找一个派生，或归约的定义，寻找一个派生，或归约一、有穷状态自动机定义与表示一、有穷状态自动机定义与表示自动机系统的自动机系统的结构及功能特征分析结构及功能特征分析： 1 1、字母表：系统处理的所有字符串由字母表上的字符组成；、字母表：系统处理的所有字符串由字母表上的字符组成；2 2、控制器：系统每次从输入字符串读入一个字符，并根据当前状态、控制器：系统每次从输入字符串读入一个字符，并根据当前状态和读入的字符，转入新的状态；新的状态和当前

3、状态可以相同也可不和读入的字符，转入新的状态；新的状态和当前状态可以相同也可不同；为此，系统具有有穷个状态同；为此，系统具有有穷个状态, ,并需要维护一个读指针。并需要维护一个读指针。3 3、几个特殊状态：、几个特殊状态： 一个开始状态；系统从此开始处理句子；一个开始状态；系统从此开始处理句子； 一些称之为终止状态或接受状态，系统从开始状态至此状态为一些称之为终止状态或接受状态，系统从开始状态至此状态为止，读入字符构成的字符串是语言的一个句子；系统到达这些止，读入字符构成的字符串是语言的一个句子；系统到达这些状态读入的全部字符串构成系统所能识别的语言。状态读入的全部字符串构成系统所能识别的语言

4、。有穷状态自动机定义与表示有穷状态自动机定义与表示有穷状态自动机装置的物理模型：有穷状态自动机装置的物理模型： 有穷状态自动机定义与表示有穷状态自动机定义与表示有穷状态自动机装置的组成：有穷状态自动机装置的组成： 1、一个具有一系列方格的输入字符串的带子：方格中存放字、一个具有一系列方格的输入字符串的带子：方格中存放字符，字符从输入带左端开始存放，符，字符从输入带左端开始存放，输入带右端无穷输入带右端无穷； 2、一个有穷状态控制器、一个有穷状态控制器 FSC：控制一个读头；每读入一个字：控制一个读头；每读入一个字符，读头右移一格，指向下一个待读入字符。符，读头右移一格，指向下一个待读入字符。有

5、穷状态控制器有穷状态控制器 FSC 的基本工作过程：的基本工作过程： 控制器执行动作由三个节拍组成：控制器执行动作由三个节拍组成： 读头读入当前指向的字读头读入当前指向的字符；符； 根据读入的字符和其自身当前状态，改变有穷状态控制根据读入的字符和其自身当前状态，改变有穷状态控制器的状态；器的状态； 读头右移一格指向下一个字符。读头右移一格指向下一个字符。有穷状态自动机定义与表示有穷状态自动机定义与表示8有穷状态自动机定义有穷状态自动机定义与表示与表示(q0, 0)=q1 (q0, 1) = q3 (q0, 2) = q3 (q1, 0)=q2 (q1, 1) = q3 (q1, 2) = q3

6、 (q2, 0)=q1 (q2, 1) = q3 (q2, 2) = q3 (q3, 0)=q3 (q3, 1) = q3 (q3, 2) = q3 状态表表示法：状态表表示法：状态图表示法：状态图表示法：q0q3q1q2 1, 2 1, 2 1,2 00 0,1,2 0012状态说明状态说明q0q1q3q3 开始状态开始状态q1q2q3q3q2q1q3q3终止状态终止状态q3q3q3q3有穷状态自动机有穷状态自动机定义与定义与表示表示函数表示法：函数表示法：有穷状态自动机有穷状态自动机定义与表示定义与表示注：状态转移图中可能存在一些并行弧，其从同一节点出发，到达同注：状态转移图中可能存在一些

7、并行弧，其从同一节点出发，到达同一节点。一节点。11一个例子一个例子:分析：目标是构造一个分析：目标是构造一个DFA，识别串，识别串x是是否有连续的否有连续的3个个0作为结尾作为结尾.状态状态0. 目目前已经读入了前已经读入了0个个0，即，即 xxxx1或或1状态状态1. 目目前已经读入了前已经读入了1个个0，即，即 xxxx10或或0状态状态2. 目目前已经读入了前已经读入了2个个0，即，即 xxxx100或或00状态状态3. 目目前已经读入了前已经读入了3个个0，即，即 xxxx1000或或0000001S1有穷状态自动机定义有穷状态自动机定义与表示与表示关于关于 FA 的几个基本概念：的

8、几个基本概念：1、基于字符串的状态转移函数、基于字符串的状态转移函数2、FA 的瞬时（即时）描述的瞬时（即时）描述3、FA 状态对读入字符串的存储功能状态对读入字符串的存储功能4、何谓、何谓 FA 识别一个句子或语言识别一个句子或语言5、FA 的等价性的等价性有穷状态自动机定义有穷状态自动机定义与表示（与表示（1）定义定义3.1的补充定义：的补充定义：有穷状态自动机定义有穷状态自动机定义与表示与表示读入空串读入空串读入非空串读入非空串对于任意的对于任意的 q Q, w , a ，有：，有：( q, wa ) = ( ( q, w ), a ) =( ( q, a1 a2 a3 an），）， a

9、 ) = ( ( ( q, a1 ), a2 ), an ), a ) 说明说明 1 1：DFA DFA 从状态从状态 q q 出发处理字符串出发处理字符串 wa 的状态转移过程：的状态转移过程：有穷状态自动机定义有穷状态自动机定义与表示与表示说明说明 2：由于由于 Q是是 Q* 的真子集；对于任意输入字符的真子集；对于任意输入字符 a，有，有 ( q, a ) = ( q, a ) 是单位元素是单位元素 = ( ( q, ), a ) 由补充定义第由补充定义第 2 条条 =( q, a ) 由补充定义第由补充定义第 1 条条有穷状态自动机定义有穷状态自动机定义与表示与表示可见，状态转移函数可

10、见，状态转移函数 可以涵盖描述可以涵盖描述 ，因此，不必区分的，因此，不必区分的使用使用和和 ，通常一般性地用，通常一般性地用代替代替 。定义定义 3.3：设设 FA M = ( Q, , , q0, F )，x, y*，( q0, x ) = q , x q y 称为称为 M 的一个瞬时描述（的一个瞬时描述（ID），）， 表示：表示：xy 是是 M 正在处理的一个字符串，其子串正在处理的一个字符串，其子串 x 引导引导 M 从从 q0 启动，到达状态启动，到达状态 q, M 的读头当前指向子串的读头当前指向子串 y 的首的首字符。字符。有穷状态自动机定义有穷状态自动机定义与表示（与表示（2）

11、如果如果 xqay 是是 M 一个瞬时描述一个瞬时描述, 且且 （ q, a ）= p ，则有：，则有： xqay xapy 表示表示 M 在状态在状态 q 时已处理完字符串时已处理完字符串 x；当前读入的字符为；当前读入的字符为 a且转入状态且转入状态 p, 然后将读头向右移动一格，指向字符串然后将读头向右移动一格，指向字符串 y 的首字符。的首字符。MFA M 的瞬时移动描述：的瞬时移动描述：有穷状态自动机定义有穷状态自动机定义与表示与表示FA M 的瞬时移动序列描述的瞬时移动序列描述： ：M 从已识别的字符串从已识别的字符串 出发，经过出发，经过 n 次移动，次移动，识别的字符串变为识别

12、的字符串变为 ；亦即，存在；亦即，存在 n 个个 ID 构成序列：构成序列： , 1, 2, , n-1, ，使得使得 1 . n-1 。nMMMMM有穷状态自动机定义有穷状态自动机定义与表示与表示例：例： q0 abc a q1 bc abc q3注：所有移动都在注：所有移动都在 M 中进行时，可省去中进行时，可省去 推导符中的推导符中的 M，分别记为：，分别记为：n几个特殊的瞬时移动序列描述：几个特殊的瞬时移动序列描述： ：M 的的 ID 从从 出发，经过若干步（包含零步）移动，出发，经过若干步（包含零步）移动，变成变成 。 ：M 的的 ID 从从 出发，经过至少一步移动，变成出发，经过至

13、少一步移动，变成 。 M+M ：n = 0 , = 。nM （M 没有移动）没有移动）有穷状态自动机定义有穷状态自动机定义与表示与表示FA M 瞬时移动序列描述实例：瞬时移动序列描述实例：例：例：FA M 识别输入串识别输入串1010010001，产生一，产生一 个瞬时移动描述序列：个瞬时移动描述序列：有穷状态自动机定义有穷状态自动机定义与表示与表示 有穷状态自动机定义有穷状态自动机定义与表示（与表示（3）定义定义 3-4：设有限自动机设有限自动机 FA M = , 对于对于 q Q，能引导，能引导 FA 从开始状态到达从开始状态到达 q 的字符串集合的字符串集合 set ( q ) = x

14、| x * 且且( q0, x ) = q 定义为状态定义为状态 q 对对字符串的存储能力字符串的存储能力。例：接受语言例：接受语言 L= x000 | x 0,1* x001 | x 0,1* 的的 FA M 各状态的字各状态的字符串存储能力如下：符串存储能力如下：set (q0) = x | x *, x = 或者或者 x 以以 1 结尾但不以结尾但不以 001 结尾结尾 ;set (q1) = x | x *, x = 0 或者或者 x 以以 10 结尾结尾 set (q2) = x | x *, x = 00 或者或者 x 以以 100 结尾结尾 set (q3) = x | x *,

15、 x 仅以仅以 000 结尾结尾 set (q4) = x | x *, x 仅以仅以 001 结尾结尾 L = x000 | x 0,1* x001 | x 0,1 * set (q0) = x | x *, x = 或者或者 x 以以 1 结尾但不以结尾但不以 001 结尾结尾 ;set (q1) = x | x *, x = 0 或者或者 x 以以 10 结尾结尾 set (q2) = x | x *, x = 00 或者或者 x 以以 100 结尾结尾 set (q3) = x | x *, x 仅以仅以 000 结尾结尾 set (q4) = x | x *, x 仅以仅以 001

16、结尾结尾 有穷状态自动机定义有穷状态自动机定义与表示与表示说明：说明：1、上述、上述 5 个集合两两互不相交；个集合两两互不相交；5 个集合的并正好构成个集合的并正好构成 M 识别输入字母识别输入字母表表 0，1 的克林闭包；亦即，这的克林闭包；亦即，这 5 个集合是关于个集合是关于 0, 1 * 的一个划分；的一个划分；2、此划分可由、此划分可由 M 上的一个等价关系上的一个等价关系 RM 确定，亦即，确定，亦即， x, y *， x RM y q Q, x, y set ( q )有穷状态自动机定义有穷状态自动机定义与表示（与表示（4）定义定义 3-6： 设设 M1，M2 是是 FA。如果

17、。如果 L（M1）= L（M2），则），则称称M1 与与 M2 等价。等价。有穷状态自动机定义有穷状态自动机定义与表示（与表示（5）第三章第三章 有穷状态自动机有穷状态自动机一、有穷状态自动机一、有穷状态自动机 FA FA 定义与表示定义与表示二、确定的有穷自动机二、确定的有穷自动机 DFADFA三、非确定的有穷自动机三、非确定的有穷自动机 NFANFA四、四、DFA DFA 和和 NFA NFA 的等价性的等价性五、带空移动的有穷自动机五、带空移动的有穷自动机- NFA- NFA六、六、FA FA 是正则语言的识别器是正则语言的识别器 七、七、FA FA 的变形的变形 - - 带输出的带输出

18、的 FAFA定义定义 3-7： 确定的有限自动机确定的有限自动机 ，记作，记作 DFA，为一个五元组，为一个五元组 M = ，其中，其中， Q， q0，F 的意义与的意义与 FA 定义相同；定义相同； 状态转移函数状态转移函数: Q Q 为单值映射函数，即，对为单值映射函数，即，对 q Q 和和 a , (q, a) = p 有唯一映射值；有唯一映射值；M 在状态在状态 q 下读入字符下读入字符 a， 将状态将状态 q 变成唯一状态变成唯一状态 p，读头向右移，读头向右移动一个方格，指向输入字符串的下一个字符。动一个方格，指向输入字符串的下一个字符。 二、确定的有穷自动机二、确定的有穷自动机

19、DFADFA例例1：构造一构造一DFM，使它接受语言，使它接受语言 L= x000y | x, y 0, 1 * 。语言句子结构特征分析：语言句子结构特征分析：对于任给输入字符串对于任给输入字符串 x 0, 1 *，DFA M 需逐一检查需逐一检查 x 的每个的每个字符，判断其中是否存在连续的字符，判断其中是否存在连续的 000 作为子串，有则接受作为子串，有则接受 x,然然后，继续读完字符串剩余的后缀后，继续读完字符串剩余的后缀 y。确定的有穷自动机确定的有穷自动机 DFADFAFA 的主框架分析的主框架分析 ： q0：M 的开始状态；的开始状态； q1： M在在 q q0 0 后读入后读入

20、一个一个 0，其可能是子串，其可能是子串 000 的第一个的第一个 0，记住；，记住； q2 ：M 在在 q1 后又读入一个后又读入一个 0，其可能是子串，其可能是子串 000 的第二个的第二个 0，记住；，记住； q3：M 在在q2后又读入一个后又读入一个 0，发现了子串，发现了子串 000 ，记住，此状态为终态。，记住，此状态为终态。设计设计 补足补足 FA 所缺失的其它状态：所缺失的其它状态： (q0, 0) = q1 可能读到可能读到 x 第一个第一个 0； (q0, 1) = q0 回始态重新检查；回始态重新检查； (q1, 0) = q2 可能读到可能读到 x 第二个第二个 0；

21、(q1, 1) = q0 - 回始态重新检查；回始态重新检查； (q2, 0) = q3 发现发现 x 的子串的子串 000； (q2, 1) = q0 - 回始态重新检查；回始态重新检查； (q3, 0) = q3 ， (q3, 1) = q3 - 已到达终态，继续接受字符串的后缀。已到达终态，继续接受字符串的后缀。 确定的有穷自动机确定的有穷自动机 DFADFA定义控制器的有限状态：定义控制器的有限状态：状状 态态 表表状状 态态 图图确定的有穷自动机确定的有穷自动机 DFADFADFADFA识别字符识别字符下面哪个是自动机可识别的字符？下面哪个是自动机可识别的字符？A. epsilonB

22、. 011C. 100011D. 1011ABCD011100所识别语言中同一长度的字符数所识别语言中同一长度的字符数这个自动机可接受的长度最小的字符是这个自动机可接受的长度最小的字符是2，共有两个，共有两个，01和和10。记作。记作 N(2)=2. 请问：请问：A. N(13)=16B. N(13)=84C. N(12)=14D. N(12)=624ABCD011100解：解：DFM 可定义为：可定义为： M =（ q0, q1, q2, q3 , 0, 1 , (q0, 0) = q1, (q1, 0) = q2, (q2, 0)= q3,(q3, 0)= q3,(q0, 1) = q0,

23、 (q1, 1)= q0, (q2, 1)= q0, (q3, 1)= q3 , q0， q3 ）。）。例例1：构造一构造一DFM，使它接受语言，使它接受语言 L= x000y | x, y 0, 1 * 。确定的有穷自动机确定的有穷自动机 DFADFA例例2： 构造一构造一DFM，使其接受语言，使其接受语言 L= 0n1m2k | n, m, k 1 。语言句子结构特征语言句子结构特征分析分析：0 在最前，在最前，1 在中间，在中间，2在最后，三者不可交叉出现；不可颠在最后，三者不可交叉出现；不可颠倒顺序；字符倒顺序；字符 0、1、2 的个数均不得少于的个数均不得少于 1。确定的有穷自动机确

24、定的有穷自动机 DFADFAFA 的主框架分析的主框架分析： q0：M 的开始状态；的开始状态； q1： M在在 q0 后读到至少一个后读到至少一个 0，等待读入更多个，等待读入更多个 0； q2 ：M 在在 q1 后读入至少一个后读入至少一个 1，等待读入更多个，等待读入更多个 1； q3：M 在在 q2 后读入至少一个后读入至少一个 2，等待读入更多个，等待读入更多个 1 ，此状态为终态。，此状态为终态。确定的有穷自动机确定的有穷自动机 DFADFA求识别求识别 L= 0n1m2k | n, m, k 1 的的 DFA M补足补足 FA 缺失部分：缺失部分： - 引入陷阱状态引入陷阱状态

25、qt (自锁态自锁态)：系系统一旦进入则无法离开的状态。统一旦进入则无法离开的状态。设计要点：设计要点：1、构造一个识别给定语言的、构造一个识别给定语言的 DFA 时，可先根据语言的主要特征，画时，可先根据语言的主要特征，画出该出该FA的主体框架图，然后考虑相关细节问题。的主体框架图，然后考虑相关细节问题。2、一旦、一旦 DFA 发现无法识别的语言句子，则进入陷阱状态发现无法识别的语言句子，则进入陷阱状态 qt；引入陷；引入陷阱状态可方便阱状态可方便 FA 的构造。的构造。 确定的有穷自动机确定的有穷自动机 DFADFA确定的有穷自动机确定的有穷自动机 DFADFA确定的有穷自动机确定的有穷自

26、动机 DFADFA 注注意：意：M的每个状态给出了语言的等价类，所有状态构成了语言的每个状态给出了语言的等价类，所有状态构成了语言上的一个划分上的一个划分 分析：什么是这里的分析：什么是这里的“有穷状态有穷状态”？（或者等价类）？（或者等价类）确定的有穷自动机确定的有穷自动机 DFADFA 注注意：意：M的每个状态给出了语言的等价类，所有状态构成了语言的每个状态给出了语言的等价类，所有状态构成了语言上的一个划分上的一个划分 分析：什么是这里的分析：什么是这里的“有穷状态有穷状态”？（或者等价类）？（或者等价类）这些等价类之间如何转换？（这些等价类之间如何转换？（ x xa意味着意味着 xa=

27、2*x + a）确定的有穷自动机确定的有穷自动机 DFADFA确定的有穷自动机确定的有穷自动机 DFADFA 分析：什么是这里的分析：什么是这里的“有穷状态有穷状态”？小结：小结：1、有穷自动机、有穷自动机 FA 的一般概念：的一般概念： 自动机定义自动机定义 五元组：五元组： M = ； 自动机表示方法：函数法，状态表，状态图；自动机表示方法：函数法，状态表，状态图； FA 的瞬时移动序列描述：的瞬时移动序列描述：xqay xapy 及及 n 次移动合成；次移动合成； FA 每个状态对读入字符串均具有某种存储功能：每个状态对读入字符串均具有某种存储功能：set ( q )； 能为能为 FA

28、接受的语言；接受的语言；FA 的等价等。的等价等。2、确定型有穷自动机、确定型有穷自动机 DFA 的定义及其构造：的定义及其构造： 定义：定义：DFA 的状态转移函数的状态转移函数 唯一；唯一； 构造：首先，根据语言结构特征设计构造：首先，根据语言结构特征设计 DFA 主框架，然后，运用主框架，然后，运用其它未明示的信息补足其它未明示的信息补足主框架主框架设计；设计中可增设设计；设计中可增设“陷阱状态陷阱状态”。M第三章第三章 有穷状态自动机有穷状态自动机一、有穷状态自动机一、有穷状态自动机 FA FA 定义与表示定义与表示二、确定的有穷自动机二、确定的有穷自动机 DFADFA三、非确定的有穷

29、自动机三、非确定的有穷自动机 NFANFA四、四、DFA DFA 和和 NFA NFA 的等价性的等价性五、带空移动的有穷自动机五、带空移动的有穷自动机- NFA- NFA六、六、FA FA 是正则语言的识别器是正则语言的识别器 七、七、FA FA 的变形的变形 - - 带输出的带输出的 FAFA例例 3：求接受语言求接受语言 L（M）= x | x 0,1 *，且，且 x 含有子串含有子串 00 或或 11 的的 FA。状态表状态表状态图状态图三、非确定有穷自动机三、非确定有穷自动机 NFANFA3、此时的、此时的N FA 程序应视为拥有程序应视为拥有“智能智能” ，亦即，在一给定，亦即，在

30、一给定状态下，它可根据当前从输入字符串读入的字符自动到状态下，它可根据当前从输入字符串读入的字符自动到( q, a ) 的转移状态的转移状态集合集合中选择进入一个正确的状态。中选择进入一个正确的状态。非确定有穷自动机非确定有穷自动机 NFANFA非确定有穷自动机非确定有穷自动机 NFANFA几个相关的基本概念：几个相关的基本概念：1、引入基于字符串的状态转移函数、引入基于字符串的状态转移函数；2、 NFA 接受句子及语言的条件接受句子及语言的条件3、两个、两个 NFA 的等价的等价非确定有穷自动机非确定有穷自动机 NFANFA非确定有穷自动机非确定有穷自动机 NFANFA非确定有穷自动机非确定

31、有穷自动机 NFANFA定义定义 3-8 的补充：的补充： 状态转移函数状态转移函数扩展为扩展为 对于任意的对于任意的 q Q, w , a ，有：，有：( q, wa ) = ( ( q, w ), a ) =( ( q, a1 a2 a3 an），）， a ) = ( ( ( q, a1 ), a2 ), an ), a ) 非确定有穷自动机非确定有穷自动机 NFANFA说明说明 1 1：NFA NFA 从状态从状态 q q 出发处理字符串出发处理字符串 wa 状态转移过程：状态转移过程：说明说明 2：由于由于 Q是是 Q* 的真子集；对于任意的的真子集；对于任意的 q Q，a ，有，有 ( q，a ) = ( q，a ) 是单位元素是单位元素 = pr ( q，)，使得，使得 p ( r, a ) 由定义第由定义第 2 条条 = pr q ，