计算理论与算法分析设计：CH2有穷自动机

CH2有穷自动机

11/6/202212.1确定型有穷自动机有穷状态自动机(Finite-stateAutomation简称FA)是具有离散的输入\输出系统的数学模型。系统内部具有有穷个状态，系统的状态概括了对过去输入状况的处理信息，系统只需根据当前所处的状态和面临的输入就可以决定系统的后继行为，系统处理了当前的输入后，系统的内部状态也将发生变化。电梯控制装置、文本编辑程序、编译技术中的词法分析程序，计算机以及人脑都是有穷状态系统。11/6/20222输入带：有穷控制器：运行开始时，读写头指向最左边的字符，控制器处于开始指定的初始状态根据最后的状态表明是否接受被输入的字符串11/6/20223

1-91,3,5,7,92.1确定型有穷自动机104397TAS1,3,5,7,9输入带有穷控制器读头0-911/6/20224定义2.1.1

一个确定有穷自动机DFA是一个五元组M=(K,,δ,s,F)其中，K：是非空有穷状态集,其中的每个元素称为一个状态；：是有穷输入字母表，它的每一个元素称为一个输入符号；δ

：是一个单值映射KK，也称状态转换函数，δ(q,x)=q意指：当现行状态为q，面临的输入符号为x时，将转到下一状态q，q称为q的一个后继状态；s

K称之为开始状态；FK称为终止状态集，至少由一个终止状态组成。11/6/20225

DFA转换矩阵:

该矩阵列表示状态集；输入字母表；δ（q,a）的值。即某个状态面临某列输入字符所唯一转向的下一个状态。该矩阵称为状态转换矩阵

DFA转换矩阵11/6/202262.1确定型有穷自动机

abab表2-111/6/202272.1确定型有穷自动机

abab11/6/202282.1确定型有穷自动机

11/6/202292.1确定型有穷自动机

11/6/2022102.1确定型有穷自动机qabababab表2-211/6/2022112.1确定型有穷自动机11/6/202212状态转换图一个DFA也可表示成一张状态转换图。DFA状态：用圆圈节点表示；初始状态节点：用“右向双(单)箭头”表示；终止状态节点：用“双圈”表示；状态变迁：用单向弧线表示，上面必须标记激励变迁的符号。11/6/202213练习q1q2q3000,1111101q1状态:M1有3个状态q1,q2,q3起始状态q1:用指向它的无出发点的箭头标示接受状态q2:用双圈标示转移:从一个状态指向另一个状态的箭头.运行:从起始状态开始根据输入和转移箭头进行.输出:输入读完处于接受状态则接受,否则拒绝.被M1接受的串有什么特点？M111/6/202214练习设A是DFAM接受的全部字符串组成的集合,则称A是DFAM的语言,记作L(M)=A.又称M识别A.q1q2q3000,111M1注意:无论在哪个状态,读到1后一定会进入状态q2.L(M1)={w|w是由0,1组成的字符串,至少含有一个1,

并且最后一个1后面含有偶数个0}11/6/202215有限自动机的设计(难点)把自己当作自动机需要记住的关键信息设计识别下列语言的DFA:{w{0,1}*:w含有子串001}11/6/202216课堂练习习题2.1.1设M是一台确定型有穷自动机。恰好在什么情况下eL(M)?证明你的答案。11/6/2022172.2非确定型有穷自动机11/6/202218(ab∪aba)*11/6/2022192.2非确定型有穷自动机

11/6/2022202.2非确定型有穷自动机因为:KK是一个函数,所以DFA在计算的每步以唯一的方式进入下一个状态所以有限自动机又称为确定型有限自动机(DFA)现在来引入非确定型的有限自动机(NFA)q1q2q3q40,110,10,1NFA的特点:一个输入可对应0至多个输出转移箭头上的符号可以是空串11/6/2022212.2非确定型有穷自动机

11/6/2022222.2非确定型有穷自动机例2.2.1：图2-7描述了一台非确定性有穷自动机，接受含有模式bb或bab出现的所有字符串的集合。还有几个非确定性有穷自动机也接受这个集合。11/6/2022232.2非确定型有穷自动机

11/6/202224当输入bababab时，会有几个不同的序列，如使用（q0,a,q0）和（q0,b,q0）这个输入串可以让M从q0转移到接受状态q4,(三种方法)11/6/20222511/6/2022262.2非确定型有穷自动机

11/6/2022272.2非确定型有穷自动机

11/6/20222811/6/202229

11/6/2022302.2非确定型有穷自动机

11/6/202231NFA与DFA等价定理:每个NFA都有一台等价的DFA.11/6/202232NFA的确定化:子集法对于一个NFA，由于状态转换函数是一个多值函数，因此总存在一些状态q，对于它们有(q,a)={q1,q2,q3,…qn},它们是NFA状态集合的一个子集，为了NFA转化为DFA，把状态集合{q1,q2,q3,…qn}看作一个状态A，也就是说让DFA的每一个状态代表NFA状态集合的某个子集，这个DFA使用它的状态去记录在NFA读入输入符号之后可能到达的所有状态的集合，这样就可以把NFA转化为DFA了。这种构造方法称为子集法。11/6/202233NFA的确定化:子集法(1)首先将从NFAN的初态S出发经过任意条ε弧所能到达的状态组成的集合作为确定化后的DFAM的初态S′。

(2)从S′出发，经过对任意输入符号a∈∑的状态转移所能到达的状态（包括读入输入符号a之后所有可能的ε转移所能到达的状态）所组成的集合作为M的新状态。

（3）如此重复，直到不在有新的状态出现为止。

（4）在所产生的状态中，含有原NFA终态的子集作DFA的终态。11/6/202234NFA的确定化:子集法E(q):M从状态q开始,不读入任何输入能够到达的所有状态的集合.特点:1.E(q)非空.2.包括任意次的e动作到达的所有状态.11/6/20223511/6/20223611/6/20223711/6/202238练习:P40图2-6确定化11/6/20223911/6/2022402.3有穷自动机与正则表达式11/6/2022412.3有穷自动机与正则表达式定理2.3.2一个语言是正则的当且仅当它被有穷自动机接受.11/6/2022422.3有穷自动机与正则表达式练习画出正则表达式

（a|b)*(aa|bb)(a|b)*对应的NFA11/6/202243正则表达式到NFA的转换（1）替换成（2）替换成（3）替换成11/6/202244NFA到正则表达式的转换具体操作如下：首先，对NFAM进行拓广(广义FA)，在M的状态转换图中，新设置一个唯一的开始状态S和唯一的终止状态Z，并允许状态转换图中弧上可以为正规表达式。然后，从开始状态S到原来所有的开始状态连接弧，再从原来所有的终止状态到Z状态也连接弧。修改后,构成了一个新的NFA，它只有一个初态结点S和一个终态结点Z，这个新的NFAM′显然和原NFAM等价。11/6/202245NFA到正则表达式的转换（1）替换成（2）替换成（3）替换成11/6/202246NFA到正则表达式的转换11/6/202247NFA到正则表达式的转换11/6/202248练习:P40图2-6写出正则表达式11/6/202249正则表达式的运算性质设e1、e2和e3都是上的正则表达式，则①e1e2=e2e1(交换律)②(e1e2)e3=e1(e2e3),(e1e2)e3=e1(e2e3)（结合律）③e1(e2e3)=e1e2e1e3,(e1e2)e3=e1e3e2e3（分配律）④e1=e1=e1⑤()*=(空集的闭包是空串)⑥e1=e1=

⑦e1*=e1|e1*⑧(e1*)*=e1