chapter 3-有穷状态自动机.

1、第三章、有穷状态自动机第三章、有穷状态自动机 条件：2元雪碧，3元橙汁，4元vc汁，红色圈表示接受状态。 例如：教室外面的饮料销售机，就是典型的有穷状态自动机， 投币，选择饮料，找零，出口，大家试着解析一下它的工作过 程，进行数学语言描述或者画出机器草图。 请大家上来画设计图！ 第三章、有穷状态自动机第三章、有穷状态自动机 q1 q2 2 q3 q4 3 4 余额余额 q6 q5 这就是我们天天见到的售货机，也称为自动机。 第三章、有穷状态自动机第三章、有穷状态自动机 一、有穷状态自动机的形式定义一、有穷状态自动机的形式定义 定义1、 确定的有穷状态自动机是一个五元组（Q, , , q0, F

2、 ）,其 中 (1)、 Q是有限状态集； (2) 、是字母表； (3)、 ：Q Q称为状态转换函数，它是状态集与字 母表的笛卡尔积到状态集的一个映射； (4) 、q0Q是初始状态； (5) 、 F是终止状态集。 第三章、有穷状态自动机第三章、有穷状态自动机 有穷状态自动机是具有离散输入和输出的系统的一种数学模有穷状态自动机是具有离散输入和输出的系统的一种数学模 型。型。 其主要特点有以下几个方面：其主要特点有以下几个方面： (1)、 系统具有有穷个状态，不同的状态代表不同的意义。按照 实际的需要，系统可以在不同的状态下完成规定的任务。 (2)、 我们可以将输入字符串中出现的字符汇集在一起构成一

3、个 字母表。系统处理的所有字符串都是这个字母表上的字符串。 (3) 、系统在任何一个状态下，从输入字符串中读入一个字符， 根据当前状态和读入的这个字符转到新的状态。 (4)、 系统中有一个状态，它是系统的开始状态。 (5) 、系统中还有一些状态表示它到目前为止所读入的字符构成 的字符串是语言的一个句子。 第三章、有穷状态自动机第三章、有穷状态自动机 例如例如机器运行时：机器运行时：010: reject 11: accept 010100100100100: accept 010000010010: reject : reject q1 q2 1 0,1 q1q3 1 0 0 第三章、有穷状态

4、自动机第三章、有穷状态自动机 二、设计有穷自动机二、设计有穷自动机 就是针对给定的语言，你来设计一台自动机，并且准确识别这 个语言。确定性的有穷自动机记为DFA。 定义：如果一个语言被一台有穷自动机识别，则称它是正则语 言。 例1、假设字母表为0,1，所考虑的语言由所以含有奇数个1的字 符串组成，构造一个识别这个语言的所有字符串的DFA的状 态图。 大家先设计。 第三章、有穷状态自动机第三章、有穷状态自动机 q1 q2 00 1 1 第三章、有穷状态自动机第三章、有穷状态自动机 例2、假设字母表为0,1，构造一个识别含有001子串的所有 字符串的DFA的状态图。 第三章、有穷状态自动机第三章、

5、有穷状态自动机 q1q2q3 00 1 q4 1 0,1 1 0 例2、假设字母表为0,1，构造一个识别含有001字串的所有 字符串的DFA的状态图。 第三章、有穷状态自动机第三章、有穷状态自动机 q1q2q3 00 1 q4 1 0,1 1 0 例2、假设字母表为0,1，构造一个识别含有001子串的所有 字符串的DFA的状态图。 第三章、有穷状态自动机第三章、有穷状态自动机 q2 q3 0 0,1 1 q0 1 0 q1 10 例3、假设字母表为0,1，构造一个识别从1开始以0结束的 所有字符串的DFA的状态图。 第三章、有穷状态自动机第三章、有穷状态自动机 q1 例4、假设字母表为0,1，

6、构造一个识别空集的DFA的状态图。 q1 例5、假设字母表为0,1，构造一个识别L(E)=的DFA的状态图。 第三章、有穷状态自动机第三章、有穷状态自动机 q2 q1 q3 0 0,1 1 例6、假设字母表为0,1，构造一个识别L(E)=0,的DFA的 状态图。 0,1 第三章、有穷状态自动机第三章、有穷状态自动机 q1 q2 00 1 1 比如例1的自动机的形式描述： （1）、Q=q1,q2; （2）、 =0,1； （3）、 (q1,0)=q1, (q1,1)=q2, (q2,0)=q2, (q2,1)=q1； （4）、q1为起始状态； （5）、F=q2为接受状态集。 第三章、有穷状态自动机

7、第三章、有穷状态自动机 问题（讨论）：问题（讨论）： 1、DFA如何进行运算？ 第三章、有穷状态自动机第三章、有穷状态自动机 三、正则运算三、正则运算 在算术中，基本对象是数，工具是处理数的运算，如+， ；在计算理论中，对象是语言，工具是处理语言所设计的 如下3种运算，称作正则运算。 定义：设A和B为语言，则下列3种运算称作正则运算。 （1）并：AB=x xA或x B （2）连接：AB=xy xA且x B （3）星号：A*=x1 x2xk xiA，i=1, k,k0 例1、=0,1，A=01,11，B=001,100，则 AB=01,11,001,100； AB=01001,01100,110

8、01,11100； A*=，01,11,0101,0111,1101,1111,010101，。 注意： = ， = ， *=， A = 第三章、有穷状态自动机第三章、有穷状态自动机 定义：如果一个语言被一台有穷自动机识别，则称它是正 则语言。 定义：如果DFA M1和DFA M2识别的语言分别为L(M1)和 L(M2)，且L(M1)= L(M2)，称M1与M2等价。 下面如何演绎规则？ 首先，封闭性 ： A=1,2,3关于数字的加法不封闭； N=1,2,3,关于数字的加法封闭。 那么，正则语言关于并运算，如何？ 第三章、有穷状态自动机第三章、有穷状态自动机 定理：正则语言类在并运算下封闭。

9、证明：思路：即假设A，B正则，再证明AB正则。 设自动机M1，M2分别识别A，B ，造一个M识别AB即可。 M1=（Q1,1,q1,F1), M2=（Q2,2,q2,F2),下面开始构造一个 M=（Q,q0,F)使其符合要求。 （1）Q=（r1，r2) r1A1且r2A2=Q1Q2; （2） 相同，若不同，则= 1 2; （3）转移函数：任意（r1，r2) Q，a ，令 （r1，r2) ，a）= （1 （r1，a) ， 2（r2，a）， 于是， 取M的一个状态和一个输入符号，返回M的下一个状 态; （4）q0是有序对（q1,q2); （5）F=(r1,r2) r1F1或r2F2 （注意，FF1

10、F2） 综上，我们构造了自动机M。 第三章、有穷状态自动机第三章、有穷状态自动机 该定理不仅证明了这个结论，更重要的是为我们的运算提供了方法。 例2、通过运算构造DFA： L(M)=w w含偶数个0或二个1。 解：令L(M1)=w w含偶数个0， L(M2)=w w含二个1。 则L(M)= L(M1) L(M2)，其中， q2 0 0 q01 0 q1 111 M1 第三章、有穷状态自动机第三章、有穷状态自动机 q4 1 q02 1 q3 000 q5 0,1 1 M2 M1=（Q1,1,q1,F1), M2=（Q2,2,q2,F2), （1）、Q1=q01,q1,q2 , Q2=q02,q3

11、,q4,q5; （2）、 = 0,1; （3）、转移函数1, 2如下表； （4）、q01，q02分别是M1,M2的起始状态； （5）、F1=q2， F2=q4. 第三章、有穷状态自动机第三章、有穷状态自动机 1 01 q01q1q01 q1q2q1 q2q1Q2 2 01 q02q02q3 q3q3q4 q4q4q5 q5q5q5 第三章、有穷状态自动机第三章、有穷状态自动机 下面构造M= （Q,q,F)， （1）Q=(r1,r2) r1Q1且r2Q2； （2）= 0,1； （3）转移函数 （r1,r2) ,a）= （1 （r1,a) , 2（r2，a）， 如下页表所示； （4）q0=（q01

12、，q02）是M的起始状态； （5）F=（q2,q02)，(q2,q3)，(q2,q4），(q2,q5)，(q01,q4)， (q1,q4)。 第三章、有穷状态自动机第三章、有穷状态自动机 01 （q01,q02）（q1,q02） （q01,q3） （q01,q3）（q1,q3）（q01,q4） （q01,q4）（q1,q4）（q01,q5） （q01,q02）（q1,q5）（q01,q5） （q1,q02）（q2,q02）（q1,q3） （q1,q3）（q2,q3）（q1,q4） （q1,q4）（q2,q4）（q1,q5） （q1,q5）（q2,q5）（q1,q5） （q2,q02）（q1,q

13、02）（q2,q3） （q2,q3）（q1,q3）（q2,q4） （q2,q4）（q1,q4）（q2,q5） （q2,q5）（q1,q5）（q2,q5） 第三章、有穷状态自动机第三章、有穷状态自动机 (q01，q02) 0 1 (q1，q02)(q2，q02) 0 0 11 0 1 (q2，q4) 0 0 11 (q01，q3) 0 1 (q1，q3)(q2，q3) 0 0 11 (q01，q5) 1 (q1，q5)(q2，q5) 0 11 0 0 (q01，q4)(q1，q4) 那么，还可以证明，连接运算与星运算也是封闭的。 第三章、有穷状态自动机第三章、有穷状态自动机 四、非确定性四、非确

14、定性 前面所有的有穷自动机都是确定性的，记为DFA，特点是必须每个符 号都有相应的运算结果，自然的，考虑非确定性NFA，为推广，它在 任何一点，下一个状态可能存在若干个选择。那么，区别在哪里呢？ q2 0 0 q01 0 q1 111 q2 0 q01 0, q1 0,10,1 第三章、有穷状态自动机第三章、有穷状态自动机 那么，NFA如何计算呢？ 对于一个输入串，它能以多种行进方式到达一个状态， 比如，输入01，下面是它的运算：从而，该机器识别01字符串。 q2 q01 q01 1 q1 q01 q1q2 0 0 0 1 第三章、有穷状态自动机第三章、有穷状态自动机 NFA的形式定义： 定义

15、2、 非确定的有限自动机是一个五元组（Q,q0,F ）,其中 (1) Q是有限状态集； (2) 是字母表； (3) ：Q P（Q）称为状态转换函数，它是状态集 与字母表的笛卡尔积到状态集的一个映射， = ，P（Q）为Q的幂集； (4) q0Q是初始状态； (5) F是终止状态集。 第三章、有穷状态自动机第三章、有穷状态自动机 考虑非确定性NFA，为DFA的推广，它在任何一点，下一个状态 可能存在若干个选择。那么，区别在哪里呢？主要是转移函数, 有很多计算分支，如果这些子过程中至少有一个接受，那么整个 计算接受。为了适应，大家运算一下010001110，100110， 11111111。非确定性NFA比DFA构造容易，实际上也是对能力更强 的计算模型的非确定性的一个很好的引入。 关键关键问题：问题：DFA与NFA等价吗？ 第三章、有穷状态自动机第三章、有穷状态自动机 第三章、有穷状态自动机第三章、有穷状态自动机 NFA与与DFA的的等价性等价性 NFA与DFA等价是指两种模型识别相同的语言类（正则语言）。 对于任意给定的DFA，存在一个NFA与之等价； 对于任意给定的NFA，存在一个DFA与之等价。 DFA本身就是一种NFA，所以，要证明DFA与NFA等价，只需证明 对于任意给定的NFA，存在一个DFA与之等价。 下面根据给定的NFA